P2376 [USACO09OCT]Allowance G

[USACO09OCT]Allowance G - 洛谷

对于每一枚硬币，我们要使它对答案的贡献最大化或者尽量少地影响其他硬币的贡献最大化，我们需要分类讨论：

（1）这枚硬币的面额V>=C，那么直接用它支付一个星期的零花钱；

（2）这枚硬币的面额V<=C，那么，有两种情况：

①用它与其他硬币组合，支付一个星期的零花钱；

②不与任何硬币组合，直接报废。

【重点】硬币如何与其他硬币组合？

[探究1]我们希望面额尽量大的硬币得到更多的使用，这样对答案没有贡献的硬币面额会很小。

[探究2]根据[探究1]，我们的贪心策略逐渐成型：

假设C'为凑齐一个星期的零花钱还剩多少钱？

（1）如果当前所有的面额都

（2）如果当前所有的面额有>=C'，那么，我们选取面额尽量小的硬币。

#include 
using namespace std;
#define MAXN 25
int n,c,ans;
struct Node
{
	int v,b;
}a[MAXN];
bool cmp (Node p,Node q)
{
	return p.v>q.v;
}

void Init ()
{
	scanf ("%d %d",&n,&c);
	for (int i=1;i<=n;i++)
		scanf ("%d %d",&a[i].v,&a[i].b);
	sort (a+1,a+1+n,cmp);
}

void Work ()
{
	int k=1,ans=0;
	while (a[k].v>=c) ans+=a[k++].b;
	while (1)
	{
		int tmp=c;
		for (int i=k;i<=n;i++)
			while (tmp>=a[i].v && a[i].b>0 && tmp>0)
				{tmp-=a[i].v;a[i].b--;}
		if (tmp>0)
			for (int i=n;i>=k;i--)
				if (a[i].b>0)
				{
					tmp-=a[i].v;
					a[i].b--;
					break;
				}
		if (tmp<=0) ans++;else break;
	}
	printf ("%dn",ans);
}

int main ()
{
	Init ();
	Work ();
	return 0;
}