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

欲哭无泪~~二分加贪心的思路,可就是为什么一直WA呢?谁抽空帮忙看看吧,万分感激啊~~~

Posted by Harder at 2008-07-25 00:52:53 on Problem 1505
#include<iostream>
#include<string.h>
using namespace std;

bool canDiv(int p[],long long mid,int m,int k,bool e[])
{
	int i=m-1,d=0;
	long long s=0;
	memset(e,false,sizeof(e));
	while(i>=0)
	{
		d++;
		if(d>k)
			return false;
		s=0;
		e[i]=true;
		while(i>=0)
		{
			if(s+p[i]>mid)
				break;
			s+=p[i];
			i--;
			if(k-d==i+1)
			{
				while(i>=0)
				{
					e[i]=true;
					i--;
				}
				return true;
			}
		}
	}
	return true;
}

int main()
{
	int Test=0,m=0,k=0;
	scanf("%d",&Test);
	while(Test--)
	{
		scanf("%d%d",&m,&k);
		long long max=0,min=0,mid=0;
		int p[501];
		bool e[501];
		for(int i=0;i<m;i++)
		{
			scanf("%d",&p[i]);
			max+=p[i];
			if(p[i]>min)
				min=p[i];
		}
		while(min<max)
		{
			mid=(min+max)/2;
			if(canDiv(p,mid,m,k,e))
				max=mid;
			else
				min=mid+1;
		}
		for(int i=0;i<m-1;i++)
		{
			printf("%d ",p[i]);
			if(e[i])
				printf("/ ");
		}
		printf("%d\n",p[m-1]);
	}
	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