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

这个怎么会超时,测试数据很多吗

Posted by wanglei at 2004-03-29 17:13:53 on Problem 1042
#include <iostream.h>
#include <string.h>
int main()
{
    int n,h,i,j,k,total,m,num;
    int f[30],d[30],t[30],time[30],max[30];
    int spend[30][30];

    int next,now;
    int cmp;
    
    
	 cin>>n;
	 while(n!=0){
	      memset(time,0,sizeof(time));
	      memset(max,0,sizeof(max));
	      cin>>h;
	      for(i=0;i<n;i++) cin>>f[i];
	      for(i=0;i<n;i++) cin>>d[i];
	      for(i=1;i<n;i++){
		 cin>>t[i];
		 time[i]=time[i-1]+t[i]*5;
	      }
	      num=0;
	      memset(spend,0,sizeof(spend));
	      for(i=0;i<n;i++){
		  k=(h*60-time[i])/5;
		  total=0;

		  while(k--){
		    m=0;

		    for(j=0;j<=i;j++){
		      now=f[j]-spend[i][j]*d[j];
		      if (now>0 && now>(f[m]-spend[i][m]*d[m])) m=j;
		    }
		    if ((f[m]-spend[i][m]*d[m])<=0){
		       spend[i][m]+=(k+1);
		       break;
		    }
		    total+=(f[m]-spend[i][m]*d[m]);
		    spend[i][m]++;

		  }
		  max[i]=total;
		  if (max[i]>max[num]) num=i;
		  if (max[i]==max[num]){
		     cmp=0;
		     for(j=0;j<n;j++){
		       if (spend[i][j]<spend[num][j]){
			  cmp=-1;
			  break;
		       }
		       if (spend[i][j]>spend[num][j]){
			  cmp=1;
			  break;
		       }
		     }
		     if (cmp==1) num=i;
		  }

	      }
	      for(j=0;j<n-1;j++) cout<<spend[num][j]*5<<", ";
	      cout<<spend[num][n-1]*5<<endl;
	      cout<<"Number of fish expected: ";
	      cout<<max[num]<<endl;
	      cin>>n;
	      if (n!=0) cout<<endl;
	 }
	 
    
    return 0;
}

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