小兔的话
欢迎大家在评论区留言哦~
CF10E Greedy Change
题目限制
- 时间限制：2.00s
- 内存限制：250.00MB
- 标准输入
- 标准输出
题目知识点
- 思维
题目来源
「 CodeForces」10E Greedy Change
为了方便大家阅读通畅，题目可能略有改动，保证不会造成影响
题目
题目翻译
给定 \(n\) 种货币，每种货币数量无限
现在要求以最少的货币数目表示一个正整数 \(S\)
一种方法是 DP 求一个最优解了；另一种方法是贪心：每次取当前能取的最大货币
现在你的任务是贪心是不一定最优的：找到最小的 \(S\)，使得 贪心求出的最优解 比 DP求出的最优解 差，或说明这样的 \(S\) 不存在
格式
输入格式
输入共 \(2\) 行：
第 \(1\) 行：包含一个整数 \(n\)
第 \(2\) 行：包含 \(n\) 个整数 \(a_i\)，表示每个硬币面值
输出格式
如果不存在 \(S\) 使得 贪心求出的最优解 比 DP求出的最优解 差，则输出 -1 ；否则输出最小的 \(S\)
样例
样例 \(1\)
样例输入
5
25 10 5 2 1
样例输出
-1
样例解释
不存在 \(S\) 使得 贪心求出的最优解 比 DP求出的最优解 差
样例 \(2\)
样例输入
3
4 3 1
样例输出
6
样例解释
当 \(S = 6\) 时，贪心做法求出的最优解为 \(3 \ (4 + 1 + 1)\)，DP做法求出的最优解为 \(2 \ (3 + 3)\)
提示
数据范围
对于 \(100\%\) 的数据：满足 \(1 \leq n \leq 400\)，\(1 \leq a_i(1 \leq i \leq n) \leq 10^9\)，且保证 \(a\) 数组严格降序排列且 \(a_n = 1\)
思路
首先肯定不可能枚举 \(S\)，因为题目没有告诉我们 \(S\) 的上界，暴力枚举肯定会 \(TLE\) 的
根据数据范围 \(1 \leq n \leq 400\)，\(1 \leq a_i(1 \leq i \leq n) \leq 10^9\)，可以看出应该是一个 \(O(n ^ 3)\) 或者 \(O(n ^ 2 \ \mathrm{log} \ a_i)\) 的算法
不知道怎么产生的 \(\mathrm{log} \ a_i\)，所以考虑 \(O(n ^ 3)\) 的算法
那么对于一个数值 \(S\)，什么情况下 DP 比 贪心 更优呢？
假设 \(S\) 能在 \(a_{k \in [i + 1, j]}\) 中取完后没有剩余（最少取了 \(p\) 次），而贪心取完了 \(a_i\) 后只能取 \(a_{k \in[j + 1, n]}\) 了（包括取 \(a_{k \in[j + 1, n]}\) 一共取了 \(q\) 次）；若 \(p < q\)，则贪心不是最优的
因此我们可以枚举区间 \([i, j]\)，如果满足 \(p < q\)，则找到了一个解 \(S\)；最后在所有的 \(S\) 中取最小的即可
分析
知道了大概思路，如何求 \(p\) 和 \(q\) 呢？
我们要保证 \(S\) 能在 \(a_{k \in [i + 1, j]}\) 中取完 并且 贪心取完了 \(a_i\) 后只能取 \(a_{k \in[j + 1, n]}\) 了
- 先保证前者：先选一个数 \(A\)，记 \(A\) 在 \(a_{k \in [i + 1, j]}\) 中取完之后剩下 \(B\)，那么 \(S\) 就可以是 \(A - B\)（\(A\) 如何选就要看后者了）
- 再保证后者：因为 \(B\) 是取完后剩下的，所以 \(B < a_j\)；要保证 \(S > a_i\) 且 \(S \ \mathrm{mod} \ a_i < a_j\)，不妨假设 \(S\) 只取了 \(1\) 个 \(a_i\)（因为要保证当前 \(S\) 也最小嘛），所以 \(S > a_i\) 且 \(S - a_i < a_j\)；因为 \(B < a_j\)，则 \(a_j - B \geq 1\)；因此可以选一个 \(A < a_i\)，使得 \(A + a_j - B \geq a_i\)，能保证这 \(2\) 个式子的只有 \(A = a_i - 1\) 了；得到 \(A\) 后，\(B\)、\(S\) 也就出来了
对每个区间 \([i, j]\)，按照上面的方法计算 \(p, q\) 就可以了
如果所有区间都不存在 \(p < q\) 就输出 \(-1\)
\(\mathrm{code}\)
#include <cstdio>
int Max(int a, int b) { return (a > b) ? a : b; }
int Min(int a, int b) { return (a < b) ? a : b; }
int rint()
{
int x = 0, fx = 1; char c = getchar();
while (c < '0' || c > '9') { fx ^= (c == '-' ? 1 : 0); c = getchar(); }
while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
if (!fx) return -x;
return x;
}
const int MAX_n = 400;
int n, res = 2e9;
int v[MAX_n + 5];
int main()
{
n = rint();
for (int i = 1; i <= n; i++)
v[i] = rint();
bool ok = false;
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
int dp = 0, count = 0, now = v[i] - 1; // A = v[i] - 1
for (int k = i + 1; k <= j; k++)
dp += now / v[k], now %= v[k]; // 求出 B
int temp = now = v[i] - 1 - now + v[j]; // 计算出 S, 备份一下
for (int k = 1; k <= n; k++)
count += now / v[k], now %= v[k];
if (dp + 1 < count) res = Min(res, temp), ok = true;
// dp + 1 是因为之前多加了一个 v[j]
// 若 p < q, 则 当前S 可能是答案
}
}
printf("%d\n", ok ? res : -1);
return 0;
}