NOIP 2025 第一题 糖果店 candy 题解
作者: | 更新日期:
反悔贪心或枚举。
本文首发于公众号：天空的代码世界，微信号：tiankonguse
零、背景
之前已经在《NOIP 2025 pdf 题目分享》中分享了 NOIP 2025 的题目。
这篇文章分享 NOIP 2025 第一道题「糖果店 candy」的题解。
PS：题目 pdf 已上传网盘，公众号回复 NOIP-2025 获取。
一、题目
小 X 开了一家糖果店，售卖 n 种糖果，每种糖果均有无限颗。
对于不同种类的糖果，小 X 采用了不同的促销策略。
具体地，对于第 i (1 ≤ i ≤ n) 种糖果，购买第一颗的价格为 xi 元，第二颗为 yi 元，第三颗又变回 xi 元，第四颗则为 yi 元，以此类推。
小 R 带了 m 元钱买糖果。
小 R 不关心糖果的种类，只想得到数量尽可能多的糖果。
你需要帮助小 R 求出 m 元钱能购买的糖果数量的最大值。
二、算法分析
对于每种糖果，可以发现价格关于购买次数的奇偶性呈周期性变化。
所以，每连续买两个糖果，对应的总价是不变的。
这里对购买行为进行分类：
1）批量购买：连续购买两次，价钱为两次价格之和 xy。
2）单次购买：只购买第一次，价钱为第一次价格 x。
显然，可以得到一个结论：只有一种糖果可以批量购买，其他糖果只进行单次购买。
证明：
假设最优答案中存在多种糖果都进行了批量购买。
不妨设第一种糖果批量购买的价格是 xy1，第二种批量购买的价格是 xy2，且 xy1 < xy2。
显然，把第二种糖果的批量购买全部换成第一种糖果，可以花更少的钱，从而剩余更多的钱，进而有机会购买更多的糖果。
故，可以使用第一种糖果把第二种糖果替换掉，答案可能更优。
根据证明过程，也可以推导出：批量购买时，应选择所有糖果里批量价格最小的那种，记为 xyMin。
所以，问题可以转化为：先进行 q 次批量购买，再进行 p 次单次购买，使总花费不超过 m，且购买数量 q * 2 + p 最大。
针对这个问题，有三种典型的做法。
不管哪种方案，都先对糖果按第一次购买的价格 x 从小到大排序。
第一种：反悔贪心。
先假设把所有钱都用于批量购买，然后用剩余的钱尽量进行单次购买。
如果单次购买的钱不够了，就反悔一次批量购买，把这部分钱改为单次购买，之后再继续尝试单次购买。
if (leftMoney < x) {
if (xyNum == 0) break; // 无法进一步反悔
if (x * 2 >= minXY) break; // 不会更优
xyNum--;
leftMoney += minXY;
}
第二种：枚举。
把所有单次购买的情况都枚举一遍，然后在剩余的钱里进行批量购买，求出最大值。
ans = max(ans, i + (m - sum[i]) / minXY * 2);
第三种：三分。
分析单次购买次数与答案之间的关系，可以发现这是一个凸函数。
故可以对单次购买的次数进行三分，来找到最优解。
三、代码实现
三种做法的输入部分是一样的。
vector<ll> nums;
void Solver() { //
ll n, m;
scanf("%lld%lld", &n, &m);
nums.reserve(n);
ll minXY = 1e10;
for (int i = 0; i < n; i++) {
ll x, y;
scanf("%lld%lld", &x, &y);
nums.emplace_back(x);
minXY = min(minXY, x + y);
}
sort(nums.begin(), nums.end());
printf("%lld\n", Solver(m, minXY));
}
反悔贪心的做法是先批量购买，然后用剩余的钱尝试单次购买。
// 反悔贪心，优先选择 minXY
ll Solver(ll m, ll minXY) {
int n = nums.size();
ll xyNum = m / minXY; // 贪心全部批量购买
ll leftMoney = m - xyNum * minXY; // 剩余的钱
ll xNum = 0;
ll ans = xyNum * 2;
for (auto x : nums) {
if (leftMoney < x) { // 钱不够了，反悔一次
if (xyNum == 0) break; // 无法进一步反悔
if (x * 2 >= minXY) break; // 剪枝，不会更优
xyNum--;
leftMoney += minXY;
}
if (leftMoney < x) {
break; // 剪枝，反悔一次还不够，后面的不可能更优
}
xNum++;
leftMoney -= x;
ans = max(ans, xNum + xyNum * 2);
}
return ans;
}
而枚举贪心的代码更简单，枚举后直接计算答案。
// 枚举贪心，优先选择单次购买，剩余的钱进行批量购买
ll Solver(const ll m, const ll minXY) {
int n = nums.size();
ll ans = m / minXY * 2; // 不选择 x
ll sum = 0;
for (int i = 1; i <= n; i++) { // 选择前 i 个 x
sum += nums[i - 1];
if (sum > m) break;
ans = max(ans, i + (m - sum) / minXY * 2);
}
return ans;
}
四、总结
NOIP 2025 第一题整体还是比较简单的，只要发现批量购买只会选择一种糖果，就很容易想到相关解法。
此外，输入范围最高到 10^18，记得使用 long long，这样就不会越界了。
《完》
-EOF-
本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code
本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。
