【POJ】3040 - Allowance（贪心）

点击打开题目

Allowance

Description

As a reward for record milk production, Farmer John has decided to start paying Bessie the cow a small weekly allowance. FJ has a set of coins in N (1 <= N <= 20) different denominations, where each denomination of coin evenly divides the next-larger denomination (e.g., 1 cent coins, 5 cent coins, 10 cent coins, and 50 cent coins).Using the given set of coins, he would like to pay Bessie at least some given amount of money C (1 <= C <= 100,000,000) every week.Please help him ompute the maximum number of weeks he can pay Bessie.

Input

* Line 1: Two space-separated integers: N and C * Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John's possession.

Output

* Line 1: A single integer that is the number of weeks Farmer John can pay Bessie at least C allowance

Sample Input

3 6
10 1
1 100
5 120

Sample Output

111

Hint

INPUT DETAILS: FJ would like to pay Bessie 6 cents per week. He has 100 1-cent coins,120 5-cent coins, and 1 10-cent coin. OUTPUT DETAILS: FJ can overpay Bessie with the one 10-cent coin for 1 week, then pay Bessie two 5-cent coins for 10 weeks and then pay Bessie one 1-cent coin and one 5-cent coin for 100 weeks.

Source

USACO 2005 October Silver

这个贪心题真心好，但是也挺麻烦。

如果钱数大于等于C的，那么就直接发出。如果小于 c 的，则从大往小拿，可以等于但是不能大于 c ，如果等于 c 就发出去，如果到最后也没有等于 c 的，再从小往大拿，能发就发，如果反向滚回来还不能发出去的话，剩下的钱就不能发了，直接退出就行。（实力滚键盘）

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
	__int64 v,m;
}coin[22];
bool cmp(node a,node b)
{
	return a.v > b.v;
}
int main()
{
	__int64 n,c;
	__int64 ans;
	while (~scanf ("%I64d %I64d",&n,&c))
	{
		for (int i = 0 ; i < n ; i++)
			scanf ("%I64d %I64d",&coin[i].v,&coin[i].m);
		sort (coin , coin + n , cmp);
		ans = 0;
		bool flag = true;		//是否能继续拿 
		for (int i = 0 ; i < n ; i++)
		{
			if (coin[i].v >= c)
				ans += coin[i].m;
			else		//首先从大往小拿 
			{
				while (coin[i].m)
				{
					int t = 0;		//已经拿的钱数 
					for (int j = i ; j < n ; j++)
					{
						if (!coin[j].m)		//没钱了就跳过 
							continue;
						while (coin[j].m && t < c)
						{
							t += coin[j].v;
							coin[j].m--;
						}
						if (t == c)		//如果正好发完就发了 
						{
							ans++;
							break;
						}
						else		//否则就再往下搜 
						{
							t -= coin[j].v;
							coin[j].m++;
						}
					}
					if (t == c)
						continue;
					for (int j = n - 1 ; j >= i ; j--)		//不够再从小往大拿 
					{
						if (!coin[j].m)
							continue;
						if (t + coin[j].m * coin[j].v >= c)		//够拿就拿
						{
							ans++;
							coin[j].m -= (c - t + coin[j].v - 1) / coin[j].v;
							t = c;		//管它后来是多少钱，就按c算 
							break;
						}
						else		//不够就先拿完 
						{
							t += coin[j].m * coin[j].v;
							coin[j].m = 0;
						}
					}
					if (t < c)		//如果还不够拿，则无法再发工资
					{
						flag = false; 
						break;
					}
				}
			}
			if (!flag)
				break;
		}
		printf ("%I64d\n",ans);
	}
	return 0;
}