Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
有什么更优化的方法吗?我用了堆排,然后只需要访问每一个元素一次,为什么还会超时?那位帮忙看一下。 #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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator