P14635 [NOIP2025] 糖果店 / candy（官方数据）

greedy, binary search, https://www.luogu.com.cn/problem/P14635

小 X 开了一家糖果店，售卖 $n$ 种糖果，每种糖果均有无限颗。对于不同种类的糖果，小 X 采用了不同的促销策略。具体地，对于第 $i$ ( $1 \leq i \leq n$ ) 种糖果，购买第一颗的价格为 $x_{i}$ 元，第二颗为 $y_{i}$ 元，第三颗又变回 $x_{i}$ 元，第四颗则为 $y_{i}$ 元，以此类推。

小 R 带了 $m$ 元钱买糖果。小 R 不关心糖果的种类，只想得到数量尽可能多的糖果。你需要帮助小 R 求出， $m$ 元钱能购买的糖果数量的最大值。

输入格式

输入的第一行包含两个正整数 $n, m$ ，代表糖果的种类数和小 R 的钱数。

输入的第 $i + 1$ ( $1 \leq i \leq n$ ) 行包含两个正整数 $x_{i}, y_{i}$ ，分别表示购买第 $i$ 种糖果时第奇数颗的价格和第偶数颗的价格。

输出格式

输出一行一个非负整数，表示 $m$ 元钱能购买的糖果数量的最大值。

输入 #1

2 10
4 1
3 3

输出 #1

输入 #2

输出 #2

说明/提示

【样例 1 解释】

小 R 可以购买 4 颗第一种糖果，共花费 $4 + 1 + 4 + 1 = 10$ 元。

【样例 2 解释】

小 R 可以购买 1 颗第一种糖果、1 颗第二种糖果与 6 颗第三种糖果，共花费 $1 + 2 + 12 = 15$ 元。

【样例 3】

见选手目录下的 candy/candy3.in 与 candy/candy3.ans。

该样例满足测试点 $6$ 的约束条件。

【样例 4】

见选手目录下的 candy/candy4.in 与 candy/candy4.ans。

该样例满足测试点 $8, 9$ 的约束条件。

【样例 5】

见选手目录下的 candy/candy5.in 与 candy/candy5.ans。

该样例满足测试点 $11, 12$ 的约束条件。

【样例 6】

见选手目录下的 candy/candy6.in 与 candy/candy6.ans。

该样例满足测试点 $13$ 的约束条件。

【样例 7】

见选手目录下的 candy/candy7.in 与 candy/candy7.ans。

该样例满足测试点 $17, 18$ 的约束条件。

【数据范围】

对于所有测试数据，均有：

$1 \leq n \leq 10^{5}$ ；
$1 \leq m \leq 10^{18}$ ；
对于所有 $1 \leq i \leq n$ ，均有 $1 \leq x_{i}, y_{i} \leq 10^{9}$ 。

::cute-table

测试点编号	$n \leq$	$m \leq$	特殊性质
$1$	$1$	$10$	无
$2, 3$	$2$	$20$	^
$4, 5$	$10$	^	^
$6$	$10^{2}$	$10^{2}$	A
$7$	^	^	B
$8, 9$	^	^	无
$10$	$10^{3}$	$10^{4}$	A
$11, 12$	^	^	B
$13$	^	^	无
$14$	$10^{5}$	$10^{9}$	A
$15, 16$	^	^	B
$17, 18$	^	^	无
$19, 20$	^	$10^{18}$	^

特殊性质 A：对于所有 $1 \leq i \leq n$ ，均有 $x_{i} = y_{i}$ 。

特殊性质 B：对于所有 $1 \leq i \leq n$ ，均有 $x_{i} \geq y_{i}$ 。

这里是针对 P14635 [NOIP2025] 糖果店 (Candy) 的 Python 解决方案及详细中文解释。

核心思路

这个问题本质上是一个贪心 (Greedy) 问题，结合了枚举。

成本周期分析：每种糖果的价格是循环的： $x_{i}, y_{i}, x_{i}, y_{i}, \dots$ 。购买 2 颗（一对）的总花费是 $S_{i} = x_{i} + y_{i}$ 。如果我们需要大量购买糖果，显然应该优先选择 $S_{i}$ 最小的那一种，我们称之为“主力糖果”（best）。
购买策略：
- 对于主力糖果（ $S_{b e s t}$ 最小的那种）：我们可以无限购买，成对购买最划算。
- 对于非主力糖果：我们只考虑买第一颗（价格 $x_{i}$ ）。
  - 为什么不买第二颗？因为买第二颗意味着为了凑齐一对，花费了 $x_{i} + y_{i}$ 。由于 $x_{i} + y_{i} \geq S_{b e s t}$ ，这笔钱不如拿去买主力糖果的一对更划算（或者一样划算，那归为主力也不影响）。
- 特例处理：如果 $x_{i} + y_{i}$ 最小的有多种，我们选择 $x_{i}$ 最小的作为主力（因为 $x_{i}$ 小意味着买单颗更容易，对凑零头有利）。
算法流程：
1. 遍历所有糖果，找到 $x_{i} + y_{i}$ 最小的种类，记为 best。
2. 将所有非 best 种类的第一颗价格 $x_{j}$ 放入一个列表 singles 并从小到大排序。
3. 枚举：我们可以选择购买 singles 列表中最便宜的 $k$ 个（ $0 \leq k \leq len (s i n g l e s)$ ）。
  - 计算买这 $k$ 个单颗糖果的花费。
  - 用剩余的钱去买主力糖果 best。
    - 先尽可能买“对”（每对 $S_{b e s t}$ ）。
    - 剩下的钱如果够买一颗 $x_{b e s t}$ ，则再加 1 颗。
  - 记录总数量，取所有 $k$ 情况下的最大值。

Python 代码

python

import sys

def solve():
    # 使用 sys.stdin 读取所有输入，处理大数据量时更快
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    iterator = iter(input_data)
    
    try:
        n = int(next(iterator))
        m = int(next(iterator))
    except StopIteration:
        return

    # 读取糖果数据
    # 存储格式: [(x1, y1), (x2, y2), ...]
    candies = []
    for _ in range(n):
        x = int(next(iterator))
        y = int(next(iterator))
        candies.append((x, y))

    # 1. 找到“主力糖果” (best)
    # 标准：x+y 最小。如果 x+y 相同，则 x 越小越好（因为剩下的零钱更容易买到第一颗）
    min_s = float('inf')
    best_idx = -1

    for i in range(n):
        current_s = candies[i][0] + candies[i][1]
        if current_s < min_s:
            min_s = current_s
            best_idx = i
        elif current_s == min_s:
            # 如果总和相同，选 x 更小的
            if candies[i][0] < candies[best_idx][0]:
                best_idx = i
    
    best_x, best_y = candies[best_idx]
    best_s = best_x + best_y

    # 2. 收集其他种类的第一颗糖果价格 (singles)
    singles = []
    for i in range(n):
        if i == best_idx:
            continue
        singles.append(candies[i][0])
    
    # 排序，以便贪心地选取便宜的单颗
    singles.sort()

    max_count = 0
    
    # 3. 枚举策略：先计算完全不买其他单颗的情况 (k=0)
    # 计算主力糖果能买多少
    # 剩余钱能买几对 * 2
    count_from_best = (m // best_s) * 2
    rem_m = m % best_s
    # 如果剩余钱够买主力糖果的第一颗
    if rem_m >= best_x:
        count_from_best += 1
    
    max_count = count_from_best

    # 4. 枚举购买 k 个其他单颗糖果的情况
    current_spent = 0
    for k in range(len(singles)):
        # 买第 k+1 便宜的单颗
        current_spent += singles[k]
        
        # 如果钱不够了，提前结束
        if current_spent > m:
            break
        
        # 剩余预算
        rem_m = m - current_spent
        
        # 用剩余预算买主力糖果
        # 能买多少对
        pairs = rem_m // best_s
        cnt = pairs * 2
        
        # 买完对后剩下的零钱
        leftover = rem_m % best_s
        # 够不够买主力的单颗
        if leftover >= best_x:
            cnt += 1
        
        # 总数量 = 已买的 k+1 个单颗 + 主力糖果数量
        total_candies = (k + 1) + cnt
        
        if total_candies > max_count:
            max_count = total_candies

    print(max_count)

if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度:
- 寻找 best 糖果：遍历一次 $O (N)$ 。
- 收集 singles 并排序： $O (N \log N)$ 。
- 枚举循环：循环 $N$ 次，内部计算为 $O (1)$ ，总共 $O (N)$ 。
- 总体时间复杂度为 $O (N \log N)$ 。
- 对于 $N = 10^{5}$ ，计算量约为 $10^{6}$ 级别，Python 可以轻松在 1 秒内完成。
空间复杂度:
- 存储糖果列表和单颗价格列表： $O (N)$ 。

详细解释 (针对样例 2)

输入:

步骤:

计算每种糖果的一对成本:
- 类型 1: $1 + 7 = 8$
- 类型 2: $2 + 3 = 5$
- 类型 3: $3 + 1 = 4$
主力糖果是类型 3 (Sum = 4)， $x_{b e s t} = 3, y_{b e s t} = 1$ 。
其他单颗列表 singles:
- 类型 1 的第一颗: 1
- 类型 2 的第一颗: 2
- singles = [1, 2] (排序后)
枚举过程:
- 情况 k=0 (不买其他单颗):
  - 预算 15 全买类型 3。
  - 15 // 4 = 3 对 (花费 12，得 6 颗)。
  - 剩余 3 元。 $3 \geq 3$ (类型 3 第一颗价)，再买 1 颗。
  - 总计: 7 颗。
- 情况 k=1 (买 1 个其他单颗):
  - 买 singles[0] (类型 1，价格 1)。花费 1。
  - 剩余预算: $15 - 1 = 14$ 。
  - 全买类型 3: $14 / / 4 = 3$ 对 (花费 12，得 6 颗)。
  - 剩余 2 元。 $2 < 3$ ，买不起类型 3 的单颗。
  - 总计: $1 + 6 = 7$ 颗。
- 情况 k=2 (买 2 个其他单颗):
  - 买 singles[0], singles[1] (价格 1, 2)。花费 $1 + 2 = 3$ 。
  - 剩余预算: $15 - 3 = 12$ 。
  - 全买类型 3: $12 / / 4 = 3$ 对 (花费 12，得 6 颗)。
  - 剩余 0 元。
  - 总计: $2 + 6 = 8$ 颗。
结果: 最大值是 8。

P14635 [NOIP2025] 糖果店 / candy（官方数据） ​

P14635 [NOIP2025] 糖果店 / candy（官方数据）