【HDU3348】coins

题面不贴了，http://acm.hdu.edu.cn/showproblem.php?pid=3348

取最小值就是每次从大往小取，但是最大值就不一定。因为假如从小往大取的话会出现凑不出p的情况。所以这里我们反过来思考，让最大值取出p，即令最小值取出sum-p，对剩下的sum-p进行取最小值的操作即可，注意最后用总硬币数-第二次取的数量即为答案。

#include<cstdio>
using namespace std;

const int a[6]={0,1,5,10,50,100};
int t,n,ansmin,ansmax,b[6],tot,cnt;

int main()
{
	int i,tmp;
	scanf("%d",&t);
	while (t--)
	{
		scanf("%d",&n);
		ansmin=ansmax=tot=cnt=0;
		for (i=1;i<=5;i++)
			scanf("%d",&b[i]),tot+=b[i]*a[i],cnt+=b[i];
		tmp=n;
		for (i=5;i>=1;i--)
		{
			if (tmp/a[i]>=b[i])
			{
				tmp-=a[i]*b[i];
				ansmin+=b[i];
			}
			else
			{
				ansmin+=tmp/a[i];
				tmp%=a[i];
			}
		}
		if (tmp>0)
		{
			puts("-1 -1");
			continue;
		}
		tmp=tot-n;
		for (i=5;i>=1;i--)
		{
			if (tmp/a[i]>=b[i])
			{
				tmp-=a[i]*b[i];
				ansmax+=b[i];
			}
			else
			{
				ansmax+=tmp/a[i];
				tmp%=a[i];
			}
		}
		printf("%d %d\n",ansmin,cnt-ansmax);
	}
	return 0;
}