很经典的贪心题...
代码写的很挫..时间跨度也很大..
数据规模不大,没有用堆，直接sort...
#include <iostream> #include <cstring> #include <algorithm> using namespace std; struct node { int f,d,t,num; }fish[50],fi[50]; int t1[50],res,tt[50]; int cmp(node aa,node bb) { if(aa.f==bb.f) return aa.num<bb.num; return aa.f>bb.f; } int n,h; int main() { int i,j; while(scanf("%d",&n)!=EOF&&n) { int maxn=-999,fl=-1; memset(tt,0,sizeof(tt)); scanf("%d",&h); h*=60; for(i=0;i<n;i++) { scanf("%d",&fish[i].f); fish[i].num=i; } for(i=0;i<n;i++) scanf("%d",&fish[i].d); for(i=1;i<n;i++) scanf("%d",&fish[i].t); fish[0].t=0; for(i=0;i<n;i++) { res=0; memset(t1,0,sizeof(t1)); memset(fi,0,sizeof(fi)); int tmph=h; for(j=0;j<=i;j++) { fi[j].d=fish[j].d; fi[j].f=fish[j].f; fi[j].num=j; fi[j].t=fish[j].t; } for(j=0;j<=i;j++) { tmph-=fi[j].t*5; // cout<<"fi[j].t="<<fi[j].t<<" "; // cout<<"tmph= "<<tmph<<endl; } // cout<<endl; tmph/=5; for(j=0;j<tmph;j++) { sort(fi,fi+i+1,cmp); // for(int k=0;k<=i;k++) // cout<<fi[k].f<<" "<<fi[k].num<<" "; // cout<<endl; if(fi[0].f>0) { t1[fi[0].num]+=5; res+=fi[0].f; fi[0].f-=fi[0].d; } // cout<<fi[0].num<<" "<<t1[fi[0].num]<<endl; } // cout<<"tmph "<<tmph<<endl; if(maxn<res) { maxn=res; int sum=0; for(j=0;j<=i;j++) { tt[j]=t1[j]; sum+=t1[j]; } // cout<<"tt[0]: "<<tt[0]<<endl; // cout<<"sum: "<<sum<<endl; tt[0]+=tmph*5-sum; } } for(i=0;i<n-1;i++) printf("%d, ",tt[i]); printf("%d/n",tt[n-1]); printf("Number of fish expected: %d/n/n",maxn); } return 0; }
