CF725E Too Much Money 题解
题目链接：Too Much Money
题意：
给定一件 \(c\) 元的物品，以及 \(n\) 个硬币，其中硬币的面值可以时任意价格，第 \(i\) 个硬币面值为 \(a_i\)
现在要用这 \(n\) 个硬币恰好凑出 \(c\) 元。有这样一种贪心策略：
初始选择集合 \(S\) 为空，每次选择不超过剩余所需价值的最大面值硬币并将其加入 \(S\) 中。
但是出题人表示不服，要卡掉这个算法。
他要加入任意数量的硬币，每个硬币可以是任意面值，使得最后算法不能得出合法的 \(S\) 集合。
同时他想最小化加入硬币的总价值。
输入数据：
第一行两个正整数 \(c,n\) 。第二行 \(n\) 个正整数 \(a_i\) 。
输出数据：
输出该组数据最小代价，如果出题人永远无法卡掉这个算法，那么输出
Greed is good。
首先，我们只需要一枚硬币就能卡掉错误的情况。
考虑反证法。假设需要两枚硬币 \(a,b~(a \le b)\) ，那么当前值不小于 \(a+b\) 时肯定不能卡掉，否则只需要一枚。
那么我们直接枚举 \([1,c]\) 的所有面额 \(k\)，再开个桶记录每种面额的出现次数，并用 set 维护贪心的过程即可。
由于 \(\sum_{i=1}^k i = \frac{k(k+1)}{2}\) ，所以对于每个 \(k\) 我们至多枚举 \(\sqrt{k}\) 个面额，每个面额可以 \(\mathcal{O}(1)\) 解决。
故总时间复杂度为 \(\mathcal{O}(c\sqrt{c})\)
代码：
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))
set<int> S;
int c, n, p, a[N], cnt[N], tmp[N];
bool check()
{
int now = c; p = 0;
while(now && !S.empty())
{
auto it = S.upper_bound(now); if(it == S.begin()) return true;
const int x = *prev(it); now -= x * min(now / x, cnt[x]);
tmp[++p] = x; S.erase(x);
}
if(now > 0) return true;
S.insert(tmp + 1, tmp + 1 + p); return false;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> c >> n;
rep(i, 1, n) { cin >> a[i]; ++cnt[a[i]]; S.insert(a[i]); }
rep(i, 1, c)
{
++cnt[i]; S.insert(i);
if(check()) return cout << i << '\n', 0;
if(!(--cnt[i])) S.erase(i);
}
cout << "Greed is good" << '\n';
return 0;
}参考文献：
