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。