现在的位置: 首页 > 综合 > 正文

贪心 poj2709

2013年12月06日 ⁄ 综合 ⁄ 共 677字 ⁄ 字号 评论关闭

题目链接:http://poj.org/problem?id=2709

首先是这道题的题意,让我话费了好长时间啊,可能是我的英语太差了,我一直在是三个混合的颜料的总的体积和是灰色的燃料的体积还是每个燃料都需要那个体积的大小,其实这个理解错误其实也就是算法的思想错误,因为算法的思想错误使我的上述两种思想都连测试数据过不去啊!

这道题要注意的一点是一定要1ml的进项混合得到灰颜色,而不能排完序后直接取排在第三的那个颜料的多少就得到所能配到的灰颜色的最多数,因为那个不是最多的!

下面是代码:

#include<iostream>
using namespace std;
int main()
{
	int T,i,j,n,a[15],Max;
	while(1)
	{
		cin>>T;
		if(T==0)
			break;
		Max=0;
		int t=0;
		for(i=1; i<=T; i++)
		{
			cin>>a[i];
			if(a[i]>Max)
				Max=a[i];
		}	
		cin>>n;
		if(Max%50!=0)
			t=Max/50+1;
		else
			t=Max/50;
		for(i=1; i<=T; i++)
			a[i]=t*50-a[i];
		int sum=0;
	    while(sum<n)
		{
			for(i=2; i<=T; i++)
			{
				a[0]=a[i];
				j=i-1;
				while(a[j]<a[0])
				{
					a[j+1]=a[j];
					j--;
				}
				a[j+1]=a[0];
			}
			if(a[3]==0)
			{
				t++;
				for(i=1; i<=T; i++)
					a[i]+=50;
			}
            sum++;
			a[1]--;a[2]--;a[3]--;
		}
		cout<<t<<endl;
	}
	return 0;
}

 

抱歉!评论已关闭.