贪心算法—Problem F
题意
给你一个价格，还有面值分别为1,5,10,50,100（单位：毛）纸币的数量，要你用最少数量的纸币和最多数量的凑出这个价格，输出最少和最多的数量。如果凑不出来，输出"-1 -1"。
解题思路
最少的数量要用贪心的思想，优先取面值尽量大的纸币来凑这个价格。找最多的数量的纸币问题可以转化为手里剩余的纸币最少，所以，假设手上总共有money毛，而价格为p毛，我们用手上最少的数量的纸币去凑（money-p）毛，然后再用总数量减去该最少数量即可。
感想
把求最多和最少的纸币数量都转化为一种问题感觉简便很多，用几个循环凑数即可，这样使问题得到简化。
AC代码
#include
using namespace std;
int main()
{
int T,i,j;
int p,r,k,money;
int min,max;
int a[]={1,5,10,50,100};
int b[10],c[10],d[10];
cin>>T;
for(i=0;i
{
money=0;
cin>>p;
for(j=0;j<5;j++)
{
cin>>b[j];
money+=a[j]*b[j];
}
r=p;
for(j=4;j>=0;j--)
{
if( (r/a[j]) < b[j] )
{
c[j]=r/a[j];
r-=a[j]*c[j];
}
else
{
c[j]=b[j];
r-=a[j]*c[j];
}
}
if(r!=0)
{
cout<<"-1 -1"<
}
else
{
k=money-p;
for(j=4;j>=0;j--)
{
if( (k/a[j]) < b[j] )
{
d[j]=k/a[j];
k-=a[j]*d[j];
}
else
{
d[j]=b[j];
k-=d[j]*a[j];
}
}
min=0;
max=0;
if(k==0)
{
for(j=0;j<5;j++)
{
min+=c[j];
}
for(j=0;j<5;j++)
{
max+=(b[j]-d[j]);
}
cout<
}
}
}
}