题解：P14635 [NOIP2025] 糖果店 / candy（民间数据）

Hughpig · 2025-11-29 14:15:36 · 题解

对于某种糖果，如果买了 u 颗，可以看作买了 u\bmod 2 颗价值为 x_i 的和 u-u\bmod 2 颗每两颗价值为 x_i+y_i 的糖果。

为了最大化能买的糖果数量，我们可以去最小化买的两颗两颗的糖果的价值 x_i+y_i，选这个价值最小的当作两颗两颗的价值。

现在问题变成了选择一些糖果买一颗或是不买，然后剩下的钱用来两颗两颗的买。

枚举买多少颗单个的糖，显然 x_i 越小的糖买一个越划算。

把所有糖果按照 x_i 从小到大排序，然后枚举买多少个，剩下的钱用来两个两个的买，记录一下最大能买的个数就行。

瓶颈在于排序，时间复杂度 O(n\log n)。