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 |
一直runtime error,本人崩溃了,求教,谢谢不过解题思路应该可以先快排后直接贪心,最坏是O(n^2) 以下是程序: #include <stdio.h> #include <stdlib.h> #include <time.h> #define maxn 10010 long n,P,L,ans; struct node { long dis,acq; }fuel[maxn]; void swap(struct node *t,struct node *m) { struct node tmp; tmp=*t; *t=*m; *m=tmp; } void sort(long L,long R) { srand(time(NULL)); long i=L,j=R,m=rand()%(R-L+1)+L,pick=fuel[m].dis; do{ while(i<=j&&fuel[i].dis<pick) i++; while(i<=j&&fuel[j].dis>pick) j--; if(i>j) break; swap(&fuel[i],&fuel[j]); i++;j--; }while(i<=j); if(i<=R) sort(i,R); if(j>=L) sort(L,j); } void init(void) { freopen("2431.in","r",stdin); freopen("2431.out","w",stdout); long i; scanf("%d",&n); for(i=1;i<=n;++i) scanf("%d%d",&fuel[i].dis,&fuel[i].acq); scanf("%d%d",&L,&P); for(i=1;i<=n;++i) fuel[i].dis=L-fuel[i].dis; sort(1,n); } void solve(long begin) { long i,max,x; if(P>=L) {printf("%d\n",ans);exit(0);} i=begin;max=0;x=0; while(fuel[i+1].dis<=P) { if(fuel[i+1].acq>max) {max=fuel[i+1].acq;x=i+1;} i++; } P+=max; if(max==0) {printf("-1\n");exit(0);} ans++; solve(x); } int main() { init(); ans=0; solve(0); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator