糖果店购买问题的贪心算法分析 摘要 本文针对 NOIP 2025 第一题糖果店（candy）问题，分析了一种基于优先队列的贪心算法的正确性。通过数学建模和反例构造，我们证明了该算法在特定条件下会输出且仅输出比最优解少
1 1 1 的结果，并给出了导致错误的充分必要条件。实验结果表明，在随机数据下该算法的正确率约为
99.68 % 99.68\% 99.68% ，但在精心构造的反例下会失效。
1. 问题描述 1.1 问题定义 给定
n n n 种糖果和预算
m m m ，购买第
k k k 次第
i i i 种糖果的价格为：
p i ( k ) = { x i , 若 k 为奇数 , y i , 若 k 为偶数 . p_i(k) =
\begin{cases}
x_i, & \text{若 } k \text{ 为奇数}, \\
y_i, & \text{若 } k \text{ 为偶数}.
\end{cases} p i ( k ) = { x i , y i , 若 k 为奇数 , 若 k 为偶数 . 输入 ：
n , m , { ( x i , y i ) } i = 1 n n, m, \{(x_i, y_i)\}_{i=1}^n n , m , {( x i , y i ) } i = 1 n 输出 ：最大糖果数量
1.2 标准最优解法 最优解的结构为购买
t t t 颗单糖和
k k k 对糖，总糖果数为
t + 2 k t + 2k t + 2 k ，其中：
C = min 1 ≤ i ≤ n ( x i + y i ) C = \min\limits_{1 \le i \le n} (x_i + y_i) C = 1 ≤ i ≤ n min ( x i + y i ) x ( 1 ) ≤ x ( 2 ) ≤ ⋯ ≤ x ( n ) x_{(1)} \le x_{(2)} \le \cdots \le x_{(n)} x ( 1 ) ≤ x ( 2 ) ≤ ⋯ ≤ x ( n ) S t = ∑ i = 1 t x ( i ) S_t = \sum\limits_{i=1}^t x_{(i)} S t = i = 1 ∑ t x ( i ) t t t
最优解为：
f ∗ = max 0 ≤ t ≤ n , S t ≤ m ( t + 2 ⌊ m − S t C ⌋ ) 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) f ∗ = 0 ≤ t ≤ n , S t ≤ m max ( t + 2 ⌊ C m − S t ⌋ ) 2. 贪心算法描述 该算法是待证伪正确性的算法。其核心思想是每次选择当前性价比最高的操作（购买一颗糖果或一对糖果）。性价比通过平均成本衡量：购买一颗糖果的平均成本为
x i x_i x i 或
y i y_i y i ，购买一对糖果的平均成本为
x i + y i 2 \frac{x_i + y_i}{2} 2 x i + y i 。算法通过优先队列动态选择最小成本操作。
2.1 算法伪代码 Input. n , m , list of pairs ( x i , y i ) for i = 1 , … , n Output. Maximum number of candies Method. Initialize a min-priority queue Q for i = 1 to n do Push ( x i , y i ) into Q // 单颗购买操作，成本为 x i Push ( x i + y i 2 , − 1 ) into Q // 成对购买操作，平均成本为 x i + y i 2 a n s ← 0 while Q is not empty and m > 0 do Pop the smallest element from Q , denoted as ( c o s t , e x t r a ) if e x t r a = − 1 then // 成对购买 if m ≥ 2 ⋅ c o s t then // 实际成本为 2 ⋅ c o s t k ← ⌊ m 2 ⋅ c o s t ⌋ m ← m − k ⋅ ( 2 ⋅ c o s t ) a n s ← a n s + 2 × k else // 单颗购买 if m ≥ c o s t then m ← m − c o s t a n s ← a n s + 1 Push ( e x t r a , c o s t ) into Q // 下次购买成本为 y i return a n s \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} Input. n , m , list of pairs ( x i , y i ) for i = 1 , … , n Output. Maximum number of candies Method. Initialize a min-priority queue Q for i = 1 to n do Push ( x i , y i ) into Q // 单颗购买操作，成本为 x i Push ( 2 x i + y i , − 1 ) into Q // 成对购买操作，平均成本为 2 x i + y i an s ← 0 while Q is not empty and m > 0 do Pop the smallest element from Q , denoted as ( cos t , e x t r a ) if e x t r a = − 1 then // 成对购买 if m ≥ 2 ⋅ cos t then // 实际成本为 2 ⋅ cos t k ← ⌊ 2 ⋅ cos t m ⌋ m ← m − k ⋅ ( 2 ⋅ cos t ) an s ← an s + 2 × k else // 单颗购买 if m ≥ cos t then m ← m − cos t an s ← an s + 1 Push ( e x t r a , cos t ) into Q // 下次购买成本为 y i return an s 2.2 算法思想 算法维护一个优先队列
Q Q Q ，其中每个元素代表一种购买操作的成本：
单颗购买 ：成本为 x i x_i x i y i y_i y i 成对购买 ：平均成本为 x i + y i 2 \frac{x_i + y_i}{2} 2 x i + y i
算法每次从队列中取出平均成本最小的操作执行，并更新队列。这种贪心策略旨在局部最大化糖果数量，但无法保证全局最优。
3. 错误分析 3.1 错误模式 设标准最优解为
f ∗ = t ∗ + 2 k ∗ f^* = t^* + 2k^* f ∗ = t ∗ + 2 k ∗ ，其中：
t ∗ t^* t ∗ k ∗ = ⌊ m − S t ∗ C ⌋ k^* = \left\lfloor \frac{m - S_{t^*}}{C} \right\rfloor k ∗ = ⌊ C m − S t ∗ ⌋ S t ∗ = ∑ i = 1 t ∗ x ( i ) S_{t^*} = \sum\limits_{i=1}^{t^*} x_{(i)} S t ∗ = i = 1 ∑ t ∗ x ( i )
贪心算法输出
f g = f ∗ − 1 f_g = f^* - 1 f g = f ∗ − 1 当且仅当存在单糖成本
c c c 满足以下性质：
性质 P ：
c > d t ∗ c > d_{t^*} c > d t ∗ d t ∗ = m − S t ∗ − k ∗ C d_{t^*} = m - S_{t^*} - k^* C d t ∗ = m − S t ∗ − k ∗ C t ∗ t^* t ∗ c 1 < C 2 \frac{c}{1} < \frac{C}{2} 1 c < 2 C
3.2 错误证明 当性质 P 成立时：
由于单颗购买的平均成本低于成对购买的平均成本，贪心算法优先购买该单糖。
但由于 c > d t ∗ c > d_{t^*} c > d t ∗ k ∗ k^* k ∗ k g = k ∗ − 1 k_g = k^* - 1 k g = k ∗ − 1
同时，贪心算法购买了 t g = t ∗ + 1 t_g = t^* + 1 t g = t ∗ + 1
因此，总糖果数为：
f g = ( t ∗ + 1 ) + 2 ( k ∗ − 1 ) = t ∗ + 2 k ∗ − 1 = f ∗ − 1. f_g = (t^* + 1) + 2(k^* - 1) = t^* + 2k^* - 1 = f^* - 1. f g = ( t ∗ + 1 ) + 2 ( k ∗ − 1 ) = t ∗ + 2 k ∗ − 1 = f ∗ − 1.
3.3 反例验证 考虑反例：
n = 2 , m = 13 , ( x 1 , y 1 ) = ( 11 , 2 ) , ( x 2 , y 2 ) = ( 5 , 13 ) . n = 2, \quad m = 13, \quad (x_1, y_1) = (11, 2), \quad (x_2, y_2) = (5, 13). n = 2 , m = 13 , ( x 1 , y 1 ) = ( 11 , 2 ) , ( x 2 , y 2 ) = ( 5 , 13 ) .
计算 C = min ( 11 + 2 , 5 + 13 ) = min ( 13 , 18 ) = 13 C = \min(11+2, 5+13) = \min(13, 18) = 13 C = min ( 11 + 2 , 5 + 13 ) = min ( 13 , 18 ) = 13
排序单糖成本：x ( 1 ) = 5 x_{(1)} = 5 x ( 1 ) = 5 x ( 2 ) = 11 x_{(2)} = 11 x ( 2 ) = 11
枚举 t t t
t = 0 t=0 t = 0 S 0 = 0 S_0 = 0 S 0 = 0 k = ⌊ 13 13 ⌋ = 1 k = \left\lfloor \frac{13}{13} \right\rfloor = 1 k = ⌊ 13 13 ⌋ = 1 f = 0 + 2 × 1 = 2 f = 0 + 2 \times 1 = 2 f = 0 + 2 × 1 = 2 t = 1 t=1 t = 1 S 1 = 5 S_1 = 5 S 1 = 5 k = ⌊ 13 − 5 13 ⌋ = 0 k = \left\lfloor \frac{13-5}{13} \right\rfloor = 0 k = ⌊ 13 13 − 5 ⌋ = 0 f = 1 + 0 = 1 f = 1 + 0 = 1 f = 1 + 0 = 1
最优解 f ∗ = 2 f^* = 2 f ∗ = 2
性质 P 检查：
t ∗ = 0 t^* = 0 t ∗ = 0 d t ∗ = 13 − 0 − 1 × 13 = 0 d_{t^*} = 13 - 0 - 1 \times 13 = 0 d t ∗ = 13 − 0 − 1 × 13 = 0 c = 5 c = 5 c = 5 c > 0 c > 0 c > 0 c 1 = 5 < 13 2 = 6.5 \frac{c}{1} = 5 < \frac{13}{2} = 6.5 1 c = 5 < 2 13 = 6.5 贪心算法输出 1 = 2 − 1 1 = 2 - 1 1 = 2 − 1
4. 实验验证 4.1 随机测试结果 在
2 × 10 4 2 \times 10^4 2 × 1 0 4 组随机数据下：
正确率：99.68 % 99.68\% 99.68%
错误率：0.32 % 0.32\% 0.32%
所有错误案例输出均为 f ∗ − 1 f^* - 1 f ∗ − 1
4.2 错误率分析 错误率低的原因在于性质 P 的条件苛刻：
需要存在单糖成本 c c c c > d t ∗ c > d_{t^*} c > d t ∗ c 1 < C 2 \frac{c}{1} < \frac{C}{2} 1 c < 2 C
在均匀随机数据中，d t ∗ d_{t^*} d t ∗ C C C
5. 结论 本文分析了糖果店购买问题的贪心算法，证明了其错误模式为输出
f ∗ − 1 f^* - 1 f ∗ − 1 ，并给出了导致错误的充分必要条件。该算法在随机数据中正确率较高，但无法保证全局最优。
6. 附录 标准解法代码 ：
CPP #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 ) O(n \log n) O ( n log n ) ，可处理
n ≤ 10 5 n \le 10^5 n ≤ 1 0 5 ，
m ≤ 10 18 m \le 10^{18} m ≤ 1 0 18 的数据范围。
考场代码 ：
CPP #include <bits/stdc++.h>
using namespace std;
const int maxn = 100004 ;
int n;
long long m;
int main ()
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 ();
if (u.second == -1 )
{
if (m - u.first < 0 )
{
pq.pop ();
continue ;
}
long long cost = 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 ;
}