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

请教各位高手,小弟不知道错什么,但是测试用例都过,0的情况都好像没问题,救命啊,谢谢

Posted by 200530691008 at 2007-08-06 00:18:54 on Problem 1042
#include "stdio.h"
#define MAX 100
int n,h,f[MAX],d[MAX],t[MAX],minute[MAX];

int difference(int a,int n,int d)//n denote rest,
{
	if(d==0)
		return a*n;
	if(n>(a/(-1*d)+1))
		return (a/(-1*d)+1)*(a+a%(-1*d))/2;
	else
		return n*(2*a+(n-1)*d)/2;
}


void fishing()
{
	int fish=0,i,s[MAX],rest=h*12,temp=0,k,j,k1=0,tempk=0,most=0;
	for(i=0;i<n;i++)
	{
		s[i]=0;
		minute[i]=0;
	}
	k=0;//现在位置
	k1=0;
	s[k]=1;
	//主算法
	while(rest>0)
	{
		k1=k;
		most=0;
		tempk=0;
		for(i=0;i<n;i++)
		{
			temp=0;
			if(f[i]==0)
				continue;
			if(f[i]>=f[k1])
			{
				for(j=i;j<k1;j++)
				{
					if(!s[j+1])
						temp=temp+t[j];
				}
				for(j=k1;j<i;j++)
				{
					if(!s[j+1])
						temp=temp+t[j];
				}
				//求小的等差数列长度n
				if((temp<rest)&&(difference(f[i],rest-temp,-1*d[i])>most))
				{
					k1=i;
					most=difference(f[i],rest-temp,-1*d[i]);
					tempk=temp+1;
				}
			}
		}
		if(k1!=k)
		{
			for(j=k;j<=k1;j++)
				s[j]=1;
			for(j=k1;j<=k;j++)
				s[j]=1;
			rest-=tempk;
			k=k1;
		}
		else
		{
			for(j=0;j<n;j++)
			{
				if((s[j]==1)&&(f[j]!=0))
					break;
			}
			if(j==n)
			{
				minute[0]+=rest;
				break;
			}
			else
				rest--;
		}
		fish+=f[k1];
		f[k1]-=d[k1];
		minute[k1]++;
		if(f[k1]<0)
			f[k1]=0;
	}
	//主算法结束
	for(i=0;i<n-1;i++)
	{
		minute[i]*=5;
		printf("%d,",minute[i]);
	}
	minute[i]*=5;
	printf("%d\n",minute[i]);
	printf("Number of fish expected:%d\n\n",fish);
}

void main()
{
	int i;
	while(scanf("%d",&n),n!=0)
	{
		scanf("%d",&h);
		for(i=0;i<n;i++)
			scanf("%d",&f[i]);
		for(i=0;i<n;i++)
			scanf("%d",&d[i]);
		for(i=0;i<n-1;i++)
			scanf("%d",&t[i]);
		fishing();
	}
}

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