| ||||||||||
| 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 | |||||||||
为什么Wrong Answer呢?(贪心)//gjc
//2005-1-31
#include <iostream>
using namespace std;
int main()
{
int gf=0,T=0,N=0;//gf:GetFish
int* sp=0,*ms=0;//sp:spend ms MaxSpend
int* f=0,*d=0,*t=0,*tf=0;//tf stores f temperately
int i,nl,m,n,h,Max;
bool flag;
while(1){
//each case
cin>>n;
if(n==0) break;
cin>>h;
f=new int[n+1];
d=new int[n+1];
t=new int[n];
tf=new int[n+1];
sp=new int[n+1];
ms=new int[n+1];
for(i=1;i<=n;i++) cin>>f[i];
for(i=1;i<=n;i++) {cin>>d[i];ms[i]=0;}
for(i=1;i<=n-1;i++) cin>>t[i];
//input finished;
Max=0;
for(nl=1;nl<=n;nl++){//Walked nl lakes
T=h*60;;
gf=0;
for(i=1;i<=n;i++) {sp[i]=0;tf[i]=f[i];}
for(i=1;i<=nl-1;i++) T-=5*t[i];
while(T>=5){
m=1;
for(i=1;i<=nl;i++)//find out the max fish Geedy!!
if(tf[i]>tf[m]) m=i;
gf+=tf[m];
tf[m]-=d[m];
if(tf[m]<d[m]) tf[m]=0;
sp[m]+=5;
T-=5;
}
if(gf>Max){
Max=gf;
for(i=1;i<=n;i++) ms[i]=sp[i];
}
else if(gf==Max){
flag=false;
for(i=1;i<=n;i++){
if(sp[i]==ms[i]) continue;
else {
if(sp[i]>ms[i]) flag=true;
break;
}//else
}//for
if(flag) for(i=1;i<=n;i++) ms[i]=sp[i];
}//else
}//end enumours
//output
for(i=1;i<=n;i++) cout<<ms[i]<<' ';
cout<<"\nNumber of fish expected: "<<Max<<"\n\n";
//release
delete [] f;
delete []d;
delete []tf;
delete []sp;
delete []ms;
}//end each case
return 1;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator