#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
	int p;
	int w;
	double rate;
	bool operator<(const node &a) const
	{
        if(rate<a.rate)
			return true;
		else if(rate==a.rate)
		{
			if(p>a.p)
				return true;
		}
			return false;

	}
}coin[501];
int main()
{
	int w1,w2,total,i,n,money,num,t;
	cin>>t;
	while(t--){
	cin>>w1>>w2;
	total=w2-w1;
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>coin[i].p>>coin[i].w;
		coin[i].rate=(double)(coin[i].p)/(double)coin[i].w;
	}
	if(total<=0)
	{
		printf("The minimum amount of money in the piggy-bank is 0.\n");
		continue;
	}
	sort(coin,coin+n);
	bool flag=false;
	money=0;
	for(i=0;i<n;i++)
	{
		if(total%coin[i].w==0)
		{
			money+=coin[i].p*(total/coin[i].w);
			total=0;
			flag=true;
		}
		else
		{
			num=total/coin[i].w;
			if(num<=0)
				continue;
			money+=num*coin[i].p;
			total-=num*coin[i].w;
		}
		if(total==0)
		{
			flag=true;
			break;
		}
	}
	if(flag)
		printf("The minimum amount of money in the piggy-bank is %d.\n",money);
	else
		printf("This is impossible.\n");

	}
	return 0;
}

• Re:帮忙看下，我觉得贪心也满足条件吧。也出不了什么不对的数据了 (1283) wangyues 2015-10-10 09:20:41