【贪心】NOIP2025 T1 糖果店 / candy
lcfollower
·
·
题解
:::warning[注意]{open}
本题解的代码能通过不保证正确性和数据强弱的民间数据，可能存在错误。
:::
但是做法好像跟讨论区很多做法一致，应该是对的？
感觉比 CSP-S T1 难度低一点或差不多，考察思想都是贪心，但是大家好像意见都不一样，本人都是两题 15 min 以内做完了。
Description
给定 n 个种类的糖果，你可以买每种糖果若干次，第奇数次买某个糖果需要钱 x_i，第偶数次买某个糖果需要钱 y_i，你手上有 m 块钱，求你最多能买的糖果数。
Solution
---
观察到样例解释是重复买第一个糖果，我们先猜想一下可能只有一个糖果重复买。
手玩一下发现是正确的。
:::success[证明：最多只有一个糖果会买 $\ge 2$ 次]{open}
假设有两种糖果，第一种为 $x_1$，$y_1$，第二种为 $x_2$，$y_2$（定义与题目一样）。
我们假设第一种糖果买了 $2k_1 + r_1$（$0 < k_1$，$0\le r_1\le 1$，$k_1$ 为整数）个，第二种糖果买了 $2k_2 + r_2$（$0 < k_2$，$0 \le r_2\le 1$，$k_2$ 为整数）个。
则耗费代价：
$$k_1(x_1 + y_1) + r_1\times x_1 + k_2(x_2 + y_2)+r_2\times x_2 = \left(k_1(x_1 + y_1) + k_2(x_2 + y_2) \right) + r_1\times x_1+r_2\times x_2$$
我们不妨令 $x_1 + y_1 < x_2 + y_2$。
实际上，我们可以买第一种糖果 $2k_1 + 2k_2$ 个，这样糖果的总数量不变，耗费代价：
$$2(k_1+k_2)(x_1+y_1) + r1\times x_1 + r2\times x2$$
由于我们令 $x_1 + y_1 < x_2 + y_2$，因此：
$$2(k_1+k_2)(x_1+y_1) + r1\times x_1 + r2\times x2 < \left(2k_1(x_1 + y_1) + 2k_2(x_2 + y_2) \right) + r_1\times x_1+r_2\times x_2$$
这样可以推广到多个，因此只有**至多一种**糖果买 $\ge 2$ 次。
对于 $k_1 + k_2 = 0 $ 的情况，我们可以理解为有 $0$ 种糖果买了 $\ge 2$ 次，因此这个结论在这种取值下仍然成立。
对于 $k_1 + k_2\neq 0$，$k_1 = 0$ 或 $k_2 = 0$ 的情况，我们也容易证明，就不阐述了。
:::
因此，我们假设有一种糖果会买 $\ge 2$ 次，那么这种糖果一定满足 $x_i + y_i$ 最小，其中这种糖果对答案的贡献为 $2k$（$0\le k$ 且 $k$ 为整数）。
然后对于所有的 $n$ 种糖果（注意被选上买 $\ge 2$ 次的糖果也算，就是买了 $2k$ 次之后），我们至多额外买一次，耗费代价 $x_i$，对答案的贡献为 $1$。
因此题目就转化为了：
:::info[Description1]{open}
给定一个数 $even$ 和一个序列 $\{b_i\}$，对于每个 $b_i$，你至多选一个 $b_i$，耗费 $b_i$，价值为 $1$；对于 $even$ 你可以选 $k$ 次（$0\le k$），耗费 $even\times k$，价值 $2k$。
当耗费不超过 $m$ 时，求最大的价值。
:::
这边 $k$ 的值不好搞，但是如果我们确定哪些 $b_i$ 用一次，就能求出 $k$ 了。
具体地，设我们选择的 $b_i$ 和为 $odd$，那么 $k$ 最大可以取 $\lfloor \frac{m - odd}{even}\rfloor$，此时 $2k$ 最大。
我们不妨把 $b_i$ 从小到大排序，这并不影响答案。
然后凭感觉选 $b_i$ 一定是选 $b_{[1 \dots i]}$，证明如下：
:::success[证明：选取的 $b_i$ 一定是从 $b_1$ 开始往后连续的一段，或者不选]{open}
注意这边我们已经把 $\{b_i\}$ 排序过了。
换种思路，如果我们想只用 $\{b_i\}$ 获得价值为 $c$，怎么让总价值最优？
容易发现只要 $odd$ 最小，可以为 $k$ 争取尽可能多的数量，总价值 $2k + c$。
因此我们会选择 $odd = \sum\limits_{i = 1}^c b_i$，故得证。
当然我们也可以不用 $\{b_i\}$，这个代价容易直接算。为 $\lfloor\frac{m}{even}\rfloor \times 2$。
:::
然后就做完了，完结撒花！
等等，我们是不是没有考虑每个糖果都最多买 $1$ 次？
仔细观察我代码的高亮部分或者思考一下，就能发现这种情况其实可以不用考虑，代码已经包含了。
Code
---
:::success[实现]{open}
```cpp lines=16,17,18 line-numbers
namespace lolcrying {
signed main(){
n = read() ,m = read();
up(i ,1 ,n) {
x[i] = read() ,y = read();
even = min(even ,x[i] + y); // 最小的 x[i] + y[i]。
}
sort(x + 1 ,x + 1 + n); // 排序。
ans = m / even * 2; // 不用 b。
up(i ,1 ,n) {
odd += x[i]; // 前缀累加。
if(odd > m) break; // 大于肯定不行，1 ~ i 每个糖果买一次都买不完。
ans = max(ans ,i + (m - odd) / even * 2); // 计算最大代价。
}
writeln(ans);
return 0 ;
}
}
```
:::
总结
---
这题是一道不错的贪心题（~~签到题~~），反思一下如果做不出来那是自己的贪心水平过低了。
容易发现如果是想到了去证第一个结论后面也是很好想到的。
Some hacks
---
Hack 来自 <https://www.luogu.com.cn/discuss/1207721> 帖。
没写 `if(odd > m) break;` 的：
```
3 100
100 10000
101 10000
101 10000
```
其他假掉的贪心的 Hacks 应该评测能评测出来。
如果有此类错误更多的 Hacks 我可能会补上。