P14635 NOIP 2025 T1 糖果店 假的贪心做法错误原因的分析

· · 算法·理论

糖果店购买问题的贪心算法分析

摘要

本文针对 NOIP 2025 第一题糖果店（candy）问题，分析了一种基于优先队列的贪心算法的正确性。通过数学建模和反例构造，我们证明了该算法在特定条件下会输出且仅输出比最优解少 1 的结果，并给出了导致错误的充分必要条件。实验结果表明，在随机数据下该算法的正确率约为 99.68\%，但在精心构造的反例下会失效。

1. 问题描述

1.1 问题定义

给定 n 种糖果和预算 m，购买第 k 次第 i 种糖果的价格为：

p_i(k) = \begin{cases} x_i, & \text{若 } k \text{ 为奇数}, \\ y_i, & \text{若 } k \text{ 为偶数}. \end{cases}

目标是在预算 m 内购买尽可能多的糖果。

输入：n, m, \{(x_i, y_i)\}_{i=1}^n
输出：最大糖果数量

1.2 标准最优解法

最优解的结构为购买 t 颗单糖和 k 对糖，总糖果数为 t + 2k，其中：

最优解为：

f^* = \max\limits_{0 \le t \le n, \, S_t \le m} \left( t + 2 \left\lfloor \frac{m - S_t}{C} \right\rfloor \right)

2. 贪心算法描述

该算法是待证伪正确性的算法。其核心思想是每次选择当前性价比最高的操作（购买一颗糖果或一对糖果）。性价比通过平均成本衡量：购买一颗糖果的平均成本为 x_i 或 y_i，购买一对糖果的平均成本为 \frac{x_i + y_i}{2}。算法通过优先队列动态选择最小成本操作。

2.1 算法伪代码

\begin{aligned} &\textbf{Input.}\quad n, m, \text{ list of pairs } (x_i, y_i) \text{ for } i=1,\dots,n \\ &\textbf{Output.}\quad \text{Maximum number of candies} \\ &\textbf{Method.} \\ &\quad \text{Initialize a min-priority queue } Q \\ &\quad \textbf{for } i = 1 \textbf{ to } n \textbf{ do} \\ &\quad\quad \text{Push } (x_i, y_i) \text{ into } Q \quad \text{// 单颗购买操作，成本为 } x_i \\ &\quad\quad \text{Push } \left( \frac{x_i + y_i}{2}, -1 \right) \text{ into } Q \quad \text{// 成对购买操作，平均成本为 } \frac{x_i + y_i}{2} \\ &\quad ans \gets 0 \\ &\quad \textbf{while } Q \text{ is not empty and } m > 0 \textbf{ do} \\ &\quad\quad \text{Pop the smallest element from } Q, \text{ denoted as } (cost, extra) \\ &\quad\quad \textbf{if } extra = -1 \textbf{ then} \quad \text{// 成对购买} \\ &\quad\quad\quad \textbf{if } m \ge 2 \cdot cost \textbf{ then} \quad \text{// 实际成本为 } 2 \cdot cost \\ &\quad\quad\quad\quad k \gets \left\lfloor \frac{m}{2 \cdot cost} \right\rfloor \\ &\quad\quad\quad\quad m \gets m - k \cdot (2 \cdot cost) \\ &\quad\quad\quad\quad ans \gets ans + 2 \times k \\ &\quad\quad \textbf{else} \quad \text{// 单颗购买} \\ &\quad\quad\quad \textbf{if } m \ge cost \textbf{ then} \\ &\quad\quad\quad\quad m \gets m - cost \\ &\quad\quad\quad\quad ans \gets ans + 1 \\ &\quad\quad\quad\quad \text{Push } (extra, cost) \text{ into } Q \quad \text{// 下次购买成本为 } y_i \\ &\quad \textbf{return } ans \end{aligned}

2.2 算法思想

算法维护一个优先队列 Q，其中每个元素代表一种购买操作的成本：

算法每次从队列中取出平均成本最小的操作执行，并更新队列。这种贪心策略旨在局部最大化糖果数量，但无法保证全局最优。

3. 错误分析

3.1 错误模式

设标准最优解为 f^* = t^* + 2k^*，其中：

贪心算法输出 f_g = f^* - 1 当且仅当存在单糖成本 c 满足以下性质：

性质 P：

3.2 错误证明

当性质 P 成立时：

3.3 反例验证

考虑反例：

n = 2, \quad m = 13, \quad (x_1, y_1) = (11, 2), \quad (x_2, y_2) = (5, 13).

性质 P 检查：

4. 实验验证

4.1 随机测试结果

在 2 \times 10^4 组随机数据下：

4.2 错误率分析

错误率低的原因在于性质 P 的条件苛刻：

5. 结论

本文分析了糖果店购买问题的贪心算法，证明了其错误模式为输出 f^* - 1，并给出了导致错误的充分必要条件。该算法在随机数据中正确率较高，但无法保证全局最优。

6. 附录

标准解法代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n; ll m;
    cin >> n >> m;
    vector<ll> x(n);
    ll min_pair = 1e18;
    for (int i = 0; i < n; i++) {
        ll xi, yi; cin >> xi >> yi;
        x[i] = xi;
        min_pair = min(min_pair, xi + yi);
    }
    sort(x.begin(), x.end());
    vector<ll> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + x[i];

    ll ans = 0;
    for (int t = 0; t <= n; t++) {
        if (prefix[t] > m) break;
        ll k = (m - prefix[t]) / min_pair;
        ans = max(ans, 2 * k + t);
    }
    cout << ans << endl;
    return 0;
}

该解法时间复杂度 O(n \log n)，可处理 n \le 10^5，m \le 10^{18} 的数据范围。

考场代码：

#include <bits/stdc++.h>

using namespace std;
const int maxn = 100004;
int n;
long long m;

int main()
{
    // freopen("candy7.in", "r", stdin);
    // 这个代码和场上代码一样地在第六个点输出 82 instead of 83 
    cin.tie(0); ios::sync_with_stdio(0);
    cin>>n>>m;
    priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> >> pq;
    for(int i=1;i<=n;i++)
    {
        long long x, y;
        cin>>x>>y;
        pq.push({x*2, y*2});
        pq.push({x+y, -1});
    }
    long long ans = 0;
    while(!pq.empty())
    {
        auto u = pq.top();
        // printf("m=%lld, u=(%lld, %lld)\n", m, u.first, u.second);
        if(u.second == -1)
        {
            if(m - u.first < 0)
            {
                pq.pop();
                continue;
            }
            long long cost = m/u.first;
            // printf("取出 %d 个 x_i+y_i=cost=%lld\n", cost, u.first*(m/u.first));
            m -= u.first*cost;
            ans += cost * 2;
            continue;
        }
        if(m - u.first/2 < 0) break;
        m -= u.first/2;
        ans++;
        pair<long long, long long> cur = {u.second, u.first};
        pq.pop();
        pq.push(cur);
    }
    cout<<ans<<'\n';
    return 0;
}