CF10E Greedy Change
- 题意：
CF10E
有一些大到小排列货币 \(a_{1...n}\)，每个可以选无限个，最小化凑出 \(S\) 的货币个数。
找到一个最小的hack贪心大到小选的 \(S\)。
- 结论：
设 \(G(S)\) 为 \((v_1,v_2,...v_n)\), 为贪心下每个货币选了的个数，实际上求的是满足和为 \(S\) 的最大字典序。
设 \(M(S)\) 为最优解每个货币选了的个数，实际上求的是个数最少的前提下的最大字典序。
如果存在反例 \(w\), 那么 \(M(w) < G(w)\)。
-
\(M(w)\) 和 \(G(w)\) 每位互不相同，可以理解为用零散的小的货币拼出一个完整的大货币，恰好不相交。
-
令 \(M(w)\) 的最小和最大非零位为 \(i, j\), \(M(w)\) 和 \(G(c_{i - 1} - 1)\) 的 \(1...j-1\) 为相同，第 \(j\) 位大 1。
所以可以枚举最高位的 \(j\), 这里 \(w\) 就是前 \(1...j\)位 的 \(c_{i - 1} - 1\) 加上一个 \(a_j\)。 利用 \(G(c_{i - 1} - 1) + 1\) 算出 \(M(w)\)，再算出 \(G(w)\) 比较。
int n;
cin >> n;
vector a(n);
for (ll &i : a) cin >> i;
ll ans = INF;
for (int i = 1; i < n; i ++) {
auto G = [=] (int x) {
int cnt = 0;
for (ll i : a)
cnt += x / i, x %= i;
return cnt;
};
int c = a[i - 1] - 1, now = c;
int M = 0;
for (int j = i; j < n; j ++) {
M += now / a[j];
now %= a[j];
ll w = c - now + a[j];
if (M + 1 < G(w))
ans = min(ans, w) ;
}
}
if (ans == INF) cout << -1;
else cout << ans;