Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

有什么更优化的方法吗?

Posted by ZSUKINGDOM at 2004-11-25 19:17:54 on Problem 2104
我用了堆排,然后只需要访问每一个元素一次,为什么还会超时?那位帮忙看一下。
#include <stdio.h>
const N=100001;
const M=5001;
long num[N];
struct Node
{
	long i,j,k;
};
void Filterdown(long *a,long begin,long end)
{
	long i,j,temp;
	i=begin;j=2*i+1;
	temp=a[i];
	while (j<=end)
	{
		if (j<end&&num[a[j]]>num[a[j+1]]) j++;
		if (num[temp]<=num[a[j]]) break;
		else {a[i]=a[j];i=j;j=2*i+1;}
	}
	a[i]=temp;
}
void  Heap(long *a,long end)
{
	long current=(end-2)/2;
	while (current>=0)
	{
		Filterdown(a,current,end-1);
		current--;
	}
}
void main()
{
	long n,i,j,k,order[N],ans[M];
	int m,total;
	Node group[M];
	scanf("%ld%d",&n,&m);
         //读数据
	for (i=1;i<=n;i++) scanf("%ld",&num[i]);
	for (i=0;i<m;i++) scanf("%ld%ld%ld",&group[i].i,&group[i].j,&group[i].k);
         //建堆
	for (i=0;i<n;i++) order[i]=i+1;
	Heap(order,n);

	total=m;
	for (i=n-1;i>=0;i--)
	{
		j=order[0];
		for (k=0;k<m;k++)
		{
			if (group[k].k>0&&group[k].i<=j&&group[k].j>=j)
			{
				group[k].k--;
				if (group[k].k==0)
				{
					ans[k]=num[j];
					total--;
				}
			}
		}
		if (total==0) break;
		
		order[0]=order[i];
		Filterdown(order,0,i);
	}

	for (i=0;i<m;i++) printf("%ld\n",ans[i]);
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator