题意 : 给出一些固定面值的硬币的数量、再给你一个总金额、问你最多能用多少硬币来刚好凑够这个金额、硬币数量和总金额都很大
分析 :
长春赛区的金牌题目
一开始认为除了做类似背包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;
);
;
LL c[] = {, , , , , , , , , , };
LL num[maxn], tmpNum[maxn], tot;
LL sum, tmpSum;
LL p;
LL Cal(LL n)
{
LL ret = ;
; i>=; i--){
|| i == ){
ret += * min(tmpNum[i]/, n/(c[i]*));
n -= * c[i] * min(tmpNum[i]/, n/(c[i]*));
}else{
ret += min(tmpNum[i], n / c[i]),
n -= c[i] * min(tmpNum[i], n / c[i]);
}
) return ret;
}
return INF;
}
int main(void){__stTIME();__IOPUT();
int nCase;
sci(nCase);
while(nCase--){
scl(p);
sum = tot = 0LL;
; i<=; i++){
scl(num[i]);
sum += num[i] * c[i];
tot += num[i];
}
if(sum < p) { puts("-1"); continue; }
LL mm = INF;
; _50<=; _50++){
; _500<=; _500++){
; i<=; i++)
tmpNum[i] = num[i];
tmpSum = sum;
if(_50){
] > ) tmpSum -= , tmpNum[]--;
else continue;
}
if(_500){
] > ) tmpSum -= , tmpNum[]--;
else continue;
}
) mm = min(mm, Cal(tmpSum - p) + _50 + _500);
}
}
if(mm >= INF) puts("-1");
else printf("%lld\n", tot - mm);
}
__enTIME();;}
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
}