标准解法

问题转化

每种糖果购买时价格交替为 \(x_i, y_i, x_i, y_i, \dots\)。
若购买 \(c\) 颗，则总价取决于 \(c\) 的奇偶性：

• 偶数 \(c = 2k\)：总价 \(k \cdot (x_i + y_i)\)，即 \(k\) 个“完整对”；
• 奇数 \(c = 2k+1\)：总价 \(k \cdot (x_i + y_i) + x_i\)，即 \(k\) 个完整对再加 1 颗（第一颗）。

因此可将每种糖果的购买决策拆分为两部分：

• “对物品”：每份包含 2 颗，价格 \(a_i = x_i + y_i\)，购买数量任意（无限）；
• “单颗物品”：每份包含 1 颗，价格 \(b_i = x_i\)，每种糖果最多购买 1 份（即只能买第一颗作为额外单颗）。

核心观察

1. 对物品：所有对物品的价值相同（均为 2 颗），因此为最小化花费，应 只购买价格最低的对。
   令
   \[ a_{\min} = \min_{1 \le i \le n} (x_i + y_i) \]
   则购买 \(k\) 份对物品的最低花费为 \(k \cdot a_{\min}\)。

2. 单颗物品：每种糖果只能买 1 颗，价格为 \(x_i\)。若要买 \(s\) 颗单颗，显然应选择价格最小的 \(s\) 个 \(x_i\)。
   将 \(x_i\) 升序排序，前缀和记为
   \[ \text{pref}[s] = \sum_{j=1}^{s} x_{(j)} \]
   其中 \(x_{(j)}\) 为排序后第 \(j\) 小的单颗价格。

求解买 \(T\) 颗糖的最小花费

设总共买 \(T\) 颗，其中包含 \(k\) 个对物品和 \(s\) 个单颗物品，则
\[ 2k + s = T \quad \Rightarrow \quad k = \frac{T - s}{2} \]
必须满足 \(s \equiv T \pmod{2}\)，且 \(0 \le s \le n\)，\(s \le T\)。

总花费为
\[ \text{cost}(T, s) = k \cdot a_{\min} + \text{pref}[s] = \frac{T - s}{2} \cdot a_{\min} + \text{pref}[s] \]

枚举所有可能的 \(s\)（与 \(T\) 同奇偶），取最小值即为买 \(T\) 颗糖的最小花费：
\[ \text{MinCost}(T) = \min_{\substack{0 \le s \le \min(n,T) \\ s \equiv T \pmod{2}}} \left( \frac{T - s}{2} \cdot a_{\min} + \text{pref}[s] \right) \]

二分答案

因为买得越多花费越多，最小花费随 \(T\) 单调递增（不严格）。
对答案 \(T\) 进行二分，上界为 \(m\)（每颗糖至少 1 元）。

• 若 \(\text{MinCost}(T) \le m\)，则 \(T\) 可行，尝试更大的 \(T\)；
• 否则缩小上界。

最终得到最大可行 \(T\)。

复杂度

• 排序 \(x_i\)：\(O(n \log n)\)
• 二分答案：每次 \(\text{MinCost}\) 枚举 \(O(n)\) 种 \(s\)，共 \(O(\log m)\) 次
  总时间复杂度 \(O(n \log n + n \log m)\)
• 空间复杂度 \(O(n)\)

正确性说明

对于任意固定 \(T\)，任何购买方案都对应一组 \((k, s)\)。
将所有对物品替换为价格最低的对，花费不增；将所有单颗替换为价格最小的那些，花费也不增。
因此上述枚举穷举了所有最优可能，得到的最小花费是准确的。
二分保证求得满足预算的最大颗数。