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

为什么Wrong Answer呢?(贪心)

Posted by iamgjc at 2005-01-31 20:56:26 on Problem 1042
//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:
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