题意:给出你硬币价值分别为1,5,10,20,50,100,200,500,1000,2000的数量,请找出能凑成价值为p的硬币最多的方案,输出此时的硬币数量。


题解:假设我们不考虑50,500这两个数,那么,其他的数都是前一个数的倍数,因此,只要前面有足够的硬币剩余,我们就可以将后面的硬币转换成前面的硬币来增加硬币数量。但是现在这里的50和500改变了这一性质,所以我们考虑改进这一贪心方法。

方法一:可以看出,如果50拿两个,那么就变成了100,也就凑成了前面所说的贪心方案,500同理。所以,我们可以利用上面同样的贪心方案,然后考虑一下拿硬币时候的奇偶性即可。


方法二:考虑反的方向。假如现在有足够的硬币可以凑成p,设硬币总价值为sum,那么我们只要求凑出sum-p所用硬币的最小数量,然后用总硬币数量减去即可。


代码:

方法一:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=11;
int T, p, ans;
int c[maxn];
LL sum[maxn];
int v[]={0, 1,5,10,20,50,100,200,500,1000,2000};
void solve(LL rmb, int idx, int cnt){
    if(rmb<0)return;
    if(idx==0){
        if(rmb==0)ans=max(ans, cnt);return;
    }
    LL trmb=max(0ll, rmb-sum[idx-1]);
    LL need=trmb/v[idx];
    if(trmb%v[idx])need++;  //不够的前面来凑
    if(need<=c[idx])solve(rmb-need*v[idx], idx-1, cnt+need);
    if(need+1<=c[idx])solve(rmb-(need+1)*v[idx], idx-1, cnt+need+1);    //考虑奇偶性
}
int main()
{
    scanf("%d", &T);
    while(T--){
        scanf("%d", &p);
        for(int i=1;i<maxn;i++){
            scanf("%d", &c[i]);
            sum[i]=sum[i-1]+(LL)v[i]*c[i];
        }
        ans=-1;
        solve(p, 10, 0);
        printf("%d\n", ans);
    }
    return 0;
}


方法二:

#include <bits/stdc++.h>
using namespace std;
const int maxn=11;
const int inf=0x3f3f3f3f;
int T, p, sum, cnt, ans;
int c[maxn], tc[maxn];
int v[]={0, 1,5,10,20,50,100,200,500,1000,2000};
int main()
{
    scanf("%d", &T);
    while(T--){
        scanf("%d", &p);
        cnt=0;
        sum=0;
        ans=inf;
        for(int i=1;i<maxn;i++){
            scanf("%d", &c[i]);
            tc[i]=c[i];
            sum+=c[i]*v[i];
            cnt+=c[i];
        }
        sum-=p;
        for(int i=0;i<=1;i++){  //枚举50个个数
            for(int j=0;j<=1;j++){  //枚举500的个数
                tc[5]=c[5]-i;
                tc[8]=c[8]-j;
                if(tc[5]<0||tc[8]<0)continue;
                int need=i+j;
                int tsum=sum-i*v[5]-j*v[8];
                for(int k=10;k>0;k--){
                    int give=min(tc[k], (int)tsum/v[k]);
                    if((give&1)&&(k==5||k==8))give--;   //只减去偶数个
                    if(give<0)continue;
                    tsum-=give*v[k];
                    need+=give;
                }
                if(tsum==0)ans=min(ans, need);
            }
        }
        printf("%d\n", ans==inf?-1:cnt-ans);
    }
    return 0;
}