题意 : 给出一些固定面值的硬币的数量、再给你一个总金额、问你最多能用多少硬币来刚好凑够这个金额、硬币数量和总金额都很大
分析 :
长春赛区的金牌题目
一开始认为除了做类似背包DP那样子的DP外、别无他法
时空限制下是不可能DP的
众所周知背包DP问题贪心是错的
遂认定不是贪心方向
看到题解、真香~
这种凑硬币问题、如果满足一个条件、那么贪心是正确的
当然和这道题目不一样、可贪心的是要求用最少的硬币凑出总金额
需要满足的条件是、可选择的硬币面额满足大面额是小面额的倍数
如果不满足上述条件？
那么用经典的 dp[i][j] = dp[i-1][j-w[i]] + 1 就能解决
当然指的是数据并不是很大的情况下、dp 复杂度在时空限制之内
那么如果满足上述条件呢？
直接贪心即可
从大往小一直选、能凑出就肯定是用硬量最少的、不能则不行
为什么这样子的贪心是对的呢？
首先要明白满足红字条件下一个很重要的性质
大面额硬币能够凑到的金额、因为是倍数关系、所以小面额的硬币也铁定能凑到
那能用大面额凑到的、就肯定不用小面额
比如 20 20 20 60 凑 60 这个数据、能直接用 60 凑够、那就不必用 20+20+20 了
那来一个不满足上述条件的例子 10 20 50 凑 60、从大到小、会先凑出 70、这样子又要回溯回去
类似一个 DFS 的过程、所以这样子贪心肯定是不行的、变成搜索了？
故需要满足大面额是小面额的倍数才行
还有一个很傻逼的问题、我之前还在想
如果满足了这个倍数关系条件、但是问题是要你凑最多的能用多少硬币、能不能直接贪心？
显然只有我这种蒟蒻才能提这种问题、显然不行、因为到后面还剩的硬币是大面额的、不灵活了
好了、那么回到这道题本身
问题是凑最多的硬币、直接贪不行怎么办？
那就间接贪、假设要凑出来的数目是 p 、你拥有的硬币的总额是 tot
那么你只要用最少的硬币凑出 tot - p 是不是剩下的就是最多的能凑出 p 的硬币
但是问题来了、这道题有并不是倍数关系的两组关系
20 和 50 、 200 和 500 、不满足条件了、怎么办？
如果这种关系比较少、例如这题只有两组、那么就想办法让它再次满足倍数关系
这题的方法是、枚举 50 和 500 选取的数量的奇偶性、什么意思？
枚举是否固定先选择一个 50 或者 500、然后后面的贪心过程
50 和 500 都是成对选、这样子就相当于有面额分别为 100 和 1000 、权重是 2 的硬币
那为什么这样子又是对的呢？
因为如果你凑的硬币中包含了 50 或者 500
那么其数量非奇即偶、对于偶数情况就是满足上述贪心性质相当于有面额分别为 100 和 1000 、权重是 2 的硬币
但是如果有奇数的话、那么你就提前选了、就是你让 p 提前选一个 50 或者 500 、即现在要凑 p-50 .....
这样子你后面成对枚举 50 和 500 、也就能保证 50 和 500 的数量是奇数了、挺巧妙的
那么这题就解决了、枚举 50 和 500 奇偶、然后每次 O（n）贪心
#include<bits/stdc++.h> #define LL long long #define ULL unsigned long long #define scl(i) scanf("%lld", &i) #define scll(i, j) scanf("%lld %lld", &i, &j) #define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k) #define scllll(i, j, k, l) scanf("%lld %lld %lld %lld", &i, &j, &k, &l) #define scs(i) scanf("%s", i) #define sci(i) scanf("%d", &i) #define scd(i) scanf("%lf", &i) #define scIl(i) scanf("%I64d", &i) #define scii(i, j) scanf("%d %d", &i, &j) #define scdd(i, j) scanf("%lf %lf", &i, &j) #define scIll(i, j) scanf("%I64d %I64d", &i, &j) #define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k) #define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k) #define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k) #define sciiii(i, j, k, l) scanf("%d %d %d %d", &i, &j, &k, &l) #define scdddd(i, j, k, l) scanf("%lf %lf %lf %lf", &i, &j, &k, &l) #define scIllll(i, j, k, l) scanf("%I64d %I64d %I64d %I64d", &i, &j, &k, &l) #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define lowbit(i) (i & (-i)) #define mem(i, j) memset(i, j, sizeof(i)) #define fir first #define sec second #define VI vector<int> #define ins(i) insert(i) #define pb(i) push_back(i) #define pii pair<int, int> #define VL vector<long long> #define mk(i, j) make_pair(i, j) #define all(i) i.begin(), i.end() #define pll pair<long long, long long> #define _TIME 0 #define _INPUT 0 #define _OUTPUT 0 clock_t START, END; void __stTIME(); void __enTIME(); void __IOPUT(); using namespace std; const LL INF = (1LL<<60); const int maxn = 2e3 + 10; LL c[] = {0, 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000}; LL num[maxn], tmpNum[maxn], tot; LL sum, tmpSum; LL p; LL Cal(LL n) { LL ret = 0; for(int i=10; i>=1; i--){ if(i == 5 || i == 8){ ret += 2 * min(tmpNum[i]/2, n/(c[i]*2)); n -= 2 * c[i] * min(tmpNum[i]/2, n/(c[i]*2)); }else{ ret += min(tmpNum[i], n / c[i]), n -= c[i] * min(tmpNum[i], n / c[i]); } if(n == 0) return ret; } return INF; } int main(void){__stTIME();__IOPUT(); int nCase; sci(nCase); while(nCase--){ scl(p); sum = tot = 0LL; for(int i=1; i<=10; i++){ scl(num[i]); sum += num[i] * c[i]; tot += num[i]; } if(sum < p) { puts("-1"); continue; } LL mm = INF; for(int _50=0; _50<=1; _50++){ for(int _500=0; _500<=1; _500++){ for(int i=1; i<=10; i++) tmpNum[i] = num[i]; tmpSum = sum; if(_50){ if(tmpNum[5] > 0) tmpSum -= 50, tmpNum[5]--; else continue; } if(_500){ if(tmpNum[8] > 0) tmpSum -= 500, tmpNum[8]--; else continue; } if(tmpSum - p >= 0) mm = min(mm, Cal(tmpSum - p) + _50 + _500); } } if(mm >= INF) puts("-1"); else printf("%lld ", tot - mm); } __enTIME();return 0;} void __stTIME() { #if _TIME START = clock(); #endif } void __enTIME() { #if _TIME END = clock(); cerr<<"execute time = "<<(double)(END-START)/CLOCKS_PER_SEC<<endl; #endif } void __IOPUT() { #if _INPUT freopen("in.txt", "r", stdin); #endif #if _OUTPUT freopen("out.txt", "w", stdout); #endif }