你是一名经验丰富的OI竞赛教练，用苏格拉底对话的启发式的讲法，逐步引导我理解这里面的题目的解法。一题到一题逐题讲解。

你好！很高兴能以教练的身份带你一起复盘 NOIP2025 的这套题目。既然我们要真正吸收这些题目的精华，我就不会直接把枯燥的代码和题解拍在你脸上。相反，我们会像在集训队讨论室里一样，我来提问，你来思考，我们一步步把正解“盘”出来。

准备好了吗？我们先从 T1 糖果店 开始。

【T1 题目回顾】 小 X 的糖果店里有 $n$ 种糖果，每种糖果的数量都是无限的。但价格很有意思：对于第 $i$ 种糖果，买第一颗需要 $x_i$ 元，第二颗需要 $y_i$ 元，第三颗又回到 $x_i$ 元，第四颗又是 $y_i$ 元……以此类推交替。 小 R 有 $m$ 元钱，不挑口味，只想要数量尽可能多的糖果。

你可以先想一想这个价格机制。如果我们一直逮着某一种特定的糖果 $i$ 买，它的价格呈现出怎样的规律？如果我们把这种购买行为进行“打包”总结，它可以拆分成哪两种最基本的“购买动作”？

（大胆说出你的想法，哪怕不完整也没关系！）

价格以数量2作为循环节，所以可以买奇数个或者偶数个

非常棒！一针见血，你抓住了核心规律——价格的循环节是 2。

既然如你所说，买某种糖果的总数只能是偶数个或者奇数个。那么，如果我们把“买偶数个”看作是买了很多个“循环节”，把“买奇数个”看作是买了很多个“循环节”再额外加上 1 颗糖。

为了方便我们制定后续的购买策略，我们能不能把这两种购买行为定义成两种基本的“套餐”呢？

你来试着定义一下：

1. 第一种“双人套餐”（买一个完整的循环节）：它包含几颗糖？花费是多少？对于同一种糖果 $i$，这种套餐我们最多能买多少次？
2. 第二种“单买套餐”（买奇数个时额外多出来的那 1 颗）：它包含几颗糖？花费是多少？对于同一种糖果 $i$，这种单买套餐我们最多能买多少次？

请你给我说明

没问题，这就为你揭晓。其实你刚刚已经把核心点说出来了——数量为 2 的循环。

顺着你的思路，既然价格是 $x_i, y_i, x_i, y_i$ 这样交替的，我们在真实购买时，无论买多少颗糖，其实都可以拆解为下面这两种“基本动作”：

1. “套餐”（买一个循环节）：

   • 花费：$x_i + y_i$
   • 获得糖果数：2 颗
   • 购买次数限制：无限次。（因为糖果有无限多，你可以一直买 2 颗、2 颗、2 颗……）

2. “单买”（买奇数个时多出来的那 1 颗）：

   • 花费：$x_i$
   • 获得糖果数：1 颗
   • 购买次数限制：对于同一种糖果 $i$，最多只能买 1 次。（因为如果你在同一种糖果上“单买”了 2 次，那这两颗糖实际上就凑成了 $x_i + y_i$ 的“套餐”了。买 3 颗就是 1 个套餐 + 1 个单买。）

---

下一步的思考：

现在，我们把原问题转化成了一个非常清晰的模型。你面前摆着：

• $n$ 种可以无限买的“双人套餐”（花费 $x_i+y_i$ 换 2 颗糖）；
• $n$ 种只能买一次的“单买”（花费 $x_i$ 换 1 颗糖）。

你的目标是：手里有 $m$ 元，想要买尽可能多的糖果（且不在乎糖果种类）。

这时候，贪心的直觉就要出来了！ 我来问你两个小问题，你凭直觉回答我：

1. 既然“双人套餐”可以无限次购买，而且我们只想要糖果数量最多，那如果要买套餐，我们只会选择哪一种套餐？
2. 对于那些只能买一次的“单买”（花费 $x_i$），如果是你，你会优先挑哪些买？

大胆猜猜看！

我可以先买最便宜的双人套餐，等到剩余钱不够了再买最便宜的单人套餐直到钱不够买为止

你的直觉非常棒！“先买性价比高的，再用剩下的钱补漏”是贪心算法最自然、最直观的起点。

但作为教练，我得给你出一个小小的“反例”，我们一起来做一个“捉虫”游戏。看看这个场景：

假设你有 $m = 25$ 元。糖果店有 5 种糖果：

• 糖果1：$x_1=10, y_1=10$（双人套餐 20元）
• 糖果2：$x_2=2, y_2=100$（双人套餐 102元）
• 糖果3：$x_3=3, y_3=100$（双人套餐 103元）
• 糖果4：$x_4=4, y_4=100$（双人套餐 104元）
• 糖果5：$x_5=5, y_5=100$（双人套餐 105元）

按照你刚刚的策略：

1. 最便宜的双人套餐是糖果1（20元）。你花 20 元买 1 份，得到 2 颗糖。
2. 剩下 5 元。你再去买最便宜的单人套餐：花 2元买糖果2，花 3元买糖果3。刚好花完，得到 2 颗糖。
3. 总共获得了 4 颗糖。

但是！如果你一上来就不买双人套餐，而是只买单人套餐呢？ 你花 $2+3+4+5+10 = 24$ 元，把这 5 种糖的单人套餐各买一遍，你可以得到 5 颗糖！比刚才还多 1 颗。

发现问题出在哪里了吗？ 因为有些单人套餐的 $x_i$ 实在太便宜了（比如 2、3、4、5），便宜到把它们单买，比买那个所谓“最便宜的双人套餐（20元2颗）”还要划算！可是单人套餐有个致命限制：每种只能买一次。

既然“单人套餐只能买一次，双人套餐可以无限买”，我们能不能把你的思路稍微翻转一下？

教练的提示： 如果我们事先已经决定好要买 $k$ 个单人套餐（$k$ 可以是 0 到 $n$），为了尽可能的省钱，我们肯定会挑 $x_i$ 最小的那 $k$ 种糖果买，对吧？ 买完这 $k$ 个单人套餐后，剩下的钱，我们就全部无脑用来买最便宜的双人套餐。

顺着这个思路，既然我们不知道到底买几个单人套餐最合适，我们在写代码时，可以使用怎样的一个极其简单粗暴的操作，把所有可能的情况都试一遍，然后取个最大值呢？（想想看，需要先对数组做一个什么操作？）

做一个遍历，检查买i个单人套餐的方案。需要把先把糖果按价格递增排序

太完美了！这就是这道题的满分正解（100分）。

我来为你总结一下我们刚才共同推导出的 T1 完美算法：

1. 先扫一遍所有的糖果，找出最便宜的“双人套餐”（即最小的 $x_j + y_j$），记为 mn。
2. 将所有糖果的**“单买套餐”价格（即 $x$ 数组）按从小到大排序**。
3. 从 $i = 0$ 遍历到 $n$：
   • 假设我们买前 $i$ 个最便宜的单买套餐。
   • 检查我们手里的钱 $m$ 是否够买这 $i$ 个单买套餐。如果不凑手，直接 break 结束遍历。
   • 如果够买，剩下的钱全部用来买最便宜的双人套餐。
   • 计算这种情况下的糖果总数：i + (剩余钱数 / mn) * 2。
4. 在所有遍历的情况中，取一个最大值，就是我们要的答案。

你看，这道题的本质就是一个加了点小变形的贪心。只要看破了“无限次购买 vs 单次购买”的区别，加上你最后说的“排序+遍历枚举前缀”，几行代码就能轻松拿下 $O(n \log n)$ 的满分。恭喜你，T1 成功通关！ 🎉

NOIP2025-T1~T4题解pdf

https://mp.weixin.qq.com/s/i8ctGeD6Lm8FQG1cj9__SA

公众号题解

https://mp.weixin.qq.com/s/79wkSNdKsi7TWdMxeRHdew

你好！我是你的OI教练。

这道题考察的是贪心策略与枚举的结合。虽然题目背景是糖果店，但本质上是资源分配问题。核心在于理解“无限供应”意味着我们可以利用周期性的价格 $x_i + y_i$ 来进行批量购买。

以下是符合 NOIP C++14 竞赛标准的题解代码。

核心思路回顾

1. 两种购买模式：
   • 单买模式：只买第 $i$ 种糖果的第 1 颗，花费 $x_i$。
   • 批发模式：连续买第 $i$ 种糖果的第 1、2 颗（或者 3、4 颗），花费 $x_i + y_i$。为了数量最多，我们只需关注所有种类中 $x_i + y_i$ 最小的那个值，记为 min_pair_cost。
2. 决策枚举：
   • 我们一定是优先买“单买价格”最便宜的前 $k$ 颗糖果。
   • 买完这 $k$ 颗后，剩下的钱全部用来“批发”性价比最高的糖果对（每对 2 颗）。
   • 由于 $n$ 只有 $10^5$，我们可以枚举 $k$ 从 $0$ 到 $n$，计算每种情况下的总数量，取最大值。

标准题解代码 (C++14)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 必须使用 long long，因为 m 可达 10^18，且 x_i 的累加和也会超过 int
typedef long long ll;

const ll INF = 4e18; // 设置一个比 m 大的安全极大值

int main() {
    // ============================================
    // 1. 竞赛标准 I/O 优化
    // 关闭 stdio 同步，解除 cin/cout 绑定，大幅提升读写速度
    // 对于 n = 10^5 的数据量，这一步是防止 TLE 的好习惯
    // ============================================
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll m;
    // 使用 cin 读取，若读取失败直接返回，增加代码健壮性
    if (!(cin >> n >> m)) return 0;

    // 存储所有糖果的第一颗价格 x
    vector<ll> x_list;
    x_list.reserve(n); // 预分配内存，微小优化

    // 维护购买“一对”（第一颗+第二颗）的最低成本
    ll min_pair_cost = INF;

    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        
        x_list.push_back(x);
        
        // 贪心核心 1：
        // 如果我们要大量进货，一定是盯着 (x+y) 最小的那种糖果一直买
        if (x + y < min_pair_cost) {
            min_pair_cost = x + y;
        }
    }

    // 贪心核心 2：
    // 如果我们要只买第一颗（单买），那肯定是从最便宜的 x 开始买
    // 所以对 x 进行排序
    sort(x_list.begin(), x_list.end());

    ll max_candies = 0;
    ll current_x_sum = 0;

    // ============================================
    // 3. 枚举策略
    // k 表示：我们决定“单买”前 k 便宜的第一颗糖果
    // k 的范围是 [0, n]
    // ============================================
    for (int k = 0; k <= n; k++) {
        // 如果 k > 0，说明比上一次循环多买了一颗单颗糖果
        // 累加这颗糖果的价格 (下标是 k-1)
        if (k > 0) {
            current_x_sum += x_list[k - 1];
        }

        // 剪枝 / 边界判断：
        // 如果买前 k 个单颗的钱已经超过了 m，那后面的肯定更买不起，直接退出循环
        if (current_x_sum > m) {
            break;
        }

        // 计算剩余的钱
        ll remaining_money = m - current_x_sum;

        // 贪心核心 3：
        // 用剩余的钱全部去买性价比最高的“糖果对”
        // 每对花费 min_pair_cost，包含 2 颗糖
        ll num_pairs = remaining_money / min_pair_cost;
        
        // 当前方案的总糖果数 = 单买的 k 颗 + 批发买的 (num_pairs * 2) 颗
        ll current_total = k + num_pairs * 2;

        // 更新全局最大值
        if (current_total > max_candies) {
            max_candies = current_total;
        }
    }

    cout << max_candies << endl;

    return 0;
}

👨‍🏫 教练划重点 (易错点解析)

1. 数据类型溢出：

   • 题目中 $m \le 10^{18}$，且 $x_i$ 累加可能非常大。如果使用 int 甚至计算中间结果时没转 long long，在大数据测试点（如 Test 19-20）必挂。务必全程 long long。

2. 贪心的完备性：

   • 有同学可能会想：“会不会存在一种情况，我买了一个 $x_i$，然后又买了对应的 $y_i$，但这个 $x_i+y_i$ 并不是全局最小的？”
   • 解析：如果 $x_i+y_i$ 不是最小的，那你买完 $x_i$ 后，与其花 $y_i$ 去凑一对，不如去买全局最小的那个 $x_{best}+y_{best}$。所以我们的策略（枚举 $x$ + 剩余全买最优对）覆盖了所有最优解的情况。

3. $k=0$ 的情况：

   • 不要忘记 $k=0$ 的情况，即一颗“单买”的都不选，钱全部用来买成对的。代码中循环从 0 开始正是为了覆盖这一点。

4. IO 优化：

   • 虽然 $N=10^5$ 在 1 秒内通常没问题，但养成写 ios::sync_with_stdio(false); 的习惯，在 NOIP/CSP 考场上能避免因输入输出过慢导致的无谓丢分。

你好！我是你的OI教练。这道题是 NOIP 2025 的一道模拟赛题，考察的是贪心策略和思维转换。题目看似复杂，糖果价格变来变去，但只要抓住“循环”的本质，就能找到通解。

我们不要急着写代码，先用草稿纸把思路理顺。

---

第一部分：思路提示

1. 价格模式分析： 对于第 $i$ 种糖果，价格序列是：$x_i, y_i, x_i, y_i, \dots$ 我们可以把它们看作两类购买方式：

• 零买（单买）：只买第一颗，花费 $x_i$。买了之后，如果不继续买这一种，就停在这里。
• 批发（对买）：一次买两颗（一颗奇数位，一颗偶数位），花费 $S_i = x_i + y_i$。

2. 核心贪心策略：

• 批发的选择：如果你打算买很多很多糖果，你肯定希望“平均价格”越低越好。因为每种糖果都有无限颗，所以我们如果要大量进货，一定会盯着那个 $x+y$ 最小的种类一直买。我们记 $P_{min} = \min(x_i + y_i)$。
• 零买的干扰：虽然批发 $P_{min}$ 很划算，但也许某些糖果的第一颗 $x_i$ 极其便宜（甚至比 $P_{min}$ 的一半还便宜）。这时候，先买这些便宜的“第一颗”可能更划算。

3. 决策模型： 我们可以把购买过程想象成这样：

1. 我们先从 $n$ 种糖果中，挑选出 $k$ 种，只买它们的第一颗（花费 $x$）。
2. 为了让数量最大化，这 $k$ 个 $x$ 一定是所有 $x$ 中最小的 $k$ 个。
3. 买完这 $k$ 颗后，剩下的钱我们全部用来买“性价比最高”的组合，也就是不断地买 $P_{min}$ 那个种类的糖果对。

4. 为什么不用担心 $y_i$？ 你可能会问：“如果我买了第 $i$ 种的第一颗 $x_i$，接下来该买 $y_i$ 了，万一 $y_i$ 也很便宜怎么办？”

• 注意：$x_i + y_i \ge P_{min}$ 是必然成立的（因为 $P_{min}$ 是全局最小和）。
• 既然 $x_i + y_i$ 的总价并不比 $P_{min}$ 更有优势，我们完全没有必要去买 $y_i$。我们只需要买完便宜的 $x_i$ 后，转头去买 $P_{min}$ 那个种类的对子即可（除非 $i$ 本身就是产生 $P_{min}$ 的那个种类，那买 $y_i$ 其实就是买 $P_{min}$ 的一部分，数学计算上是一样的）。

---

第二部分：预备知识点总结

1. 贪心算法 (Greedy)：理解局部最优（选最小的 $x$，选最小的 $x+y$）如何推导全局最优。
2. 前缀和 (Prefix Sum)：为了快速计算“买前 $k$ 便宜的单颗糖果要花多少钱”，我们需要先排序，再用前缀和维护。
3. 枚举与数学计算：在 $10^5$ 的数据规模下，我们可以枚举“买了多少颗单颗糖果”，剩下的用 $O(1)$ 的公式计算。
4. 数据类型：$m$ 高达 $10^{18}$，涉及金额的变量必须使用 long long。

---

第三部分：启发式教学 —— 草稿纸上的推理

现在，拿起笔，我们用样例 2 来画一画，模拟一下这个决策过程。

样例 2 数据： $m = 15$ A: 1, 7 $\to$ $x=1, x+y=8$ B: 2, 3 $\to$ $x=2, x+y=5$ C: 3, 1 $\to$ $x=3, x+y=4$

步骤一：找到“批发价”最低的 计算所有的 $x+y$：

• A: 8
• B: 5
• C: 4 $\leftarrow$ 最小！ $P_{min} = 4$。 这意味着，只要我们想，随时可以用 4 元买 2 颗糖（买 C 类）。

步骤二：整理“单买价” 把所有的 $x$ 列出来，从小到大排序： List X: [1 (A), 2 (B), 3 (C)]

步骤三：枚举方案（尝试买 k 个单买的）

• 方案 0：我不单买，只批发 C。

  • 花费单买：0
  • 剩余钱：15
  • 能买几对 C？ $15 \div 4 = 3$ 对（余 3 元）。
  • 糖果总数：$0 + 3 \times 2 = 6$ 颗。
  • （注：余下的 3 元买不起 Pmin，也买不起剩下的任何 x 组合，暂且不考虑复杂的捡漏，通常公式能覆盖）

• 方案 1：买 1 个最便宜的单买（A 的 x=1）。

  • 花费单买：1
  • 剩余钱：$15 - 1 = 14$
  • 能买几对 C？ $14 \div 4 = 3$ 对（余 2 元）。
  • 糖果总数：$1 + 3 \times 2 = 7$ 颗。
  • （比方案 0 好了！）

• 方案 2：买 2 个最便宜的单买（A 的 x=1, B 的 x=2）。

  • 花费单买：$1 + 2 = 3$
  • 剩余钱：$15 - 3 = 12$
  • 能买几对 C？ $12 \div 4 = 3$ 对（整除）。
  • 糖果总数：$2 + 3 \times 2 = 8$ 颗。
  • （更好了！）

• 方案 3：买 3 个最便宜的单买（A, B, C 的 x 全买）。

  • 花费单买：$1 + 2 + 3 = 6$
  • 剩余钱：$15 - 6 = 9$
  • 能买几对 C？ $9 \div 4 = 2$ 对（余 1 元）。
  • 糖果总数：$3 + 2 \times 2 = 7$ 颗。
  • （变差了）

结论： 最大值是 8。输出 8。

推导公式： 假设我们选了前 $k$ 便宜的 $x$，总花费为 $SumX_k$。 那么能买到的糖果数量为：

$$Ans = k + 2 \times \lfloor \frac{m - SumX_k}{P_{min}} \rfloor $$

(前提是 $m \ge SumX_k$)

你只需要写一个循环，$k$ 从 $0$ 遍历到 $n$，维护 $SumX$，套用公式取最大值即可。

快去试试把这个逻辑写成代码吧！别忘了开 long long。