[NOIP2025] 糖果店

GitHub 跳转原题关系图返回列表

把购买拆成最便宜的两颗组和若干个单颗项，预处理奇偶最优值后二分答案。

OJ: luogu

题目 ID: P14635

难度:普及+/提高

标签:二分答案贪心推导noip

日期: 2026-06-22 17:57

题意

有 n 种糖果，每种糖果数量无限。第 i 种糖果的价格按购买次数交替：

text

1x_i, y_i, x_i, y_i, ...

也就是说，买第 1,3,5,... 颗花 x_i 元，买第 2,4,6,... 颗花 y_i 元。

给定预算 m，问最多可以买多少颗糖果。只关心总数量，不关心买了哪些种类。

思路

先看一个可以直接验证想法的朴素解。它按糖果种类做小预算 DP，枚举每种糖果买多少颗：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67// brute.cpp：小数据暴力 DP，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;
const int INF = 1000000000;

int n, m;
int x[MAXN], y[MAXN];
int dp[205];

int cost_of_count(int id, int cnt) {
    int pairs = cnt / 2;
    int cost = pairs * (x[id] + y[id]);
    if (cnt % 2 == 1) {
        cost += x[id];
    }
    return cost;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    for (int j = 1; j <= m; j++) {
        dp[j] = -INF;
    }
    dp[0] = 0;

    // 逐种糖果枚举买几颗。m 很小时，每种糖果最多买 m 颗即可覆盖所有可能。
    for (int i = 1; i <= n; i++) {
        int next_dp[205];
        for (int j = 0; j <= m; j++) {
            next_dp[j] = dp[j];
        }

        for (int money = 0; money <= m; money++) {
            if (dp[money] < 0) {
                continue;
            }
            for (int cnt = 1; cnt <= m; cnt++) {
                int cost = cost_of_count(i, cnt);
                if (money + cost > m) {
                    break;
                }
                next_dp[money + cost] = max(next_dp[money + cost], dp[money] + cnt);
            }
        }

        for (int j = 0; j <= m; j++) {
            dp[j] = next_dp[j];
        }
    }

    int ans = 0;
    for (int j = 0; j <= m; j++) {
        ans = max(ans, dp[j]);
    }

    cout << ans << '\n';
    return 0;
}

这个做法能帮助理解题意，但它依赖预算大小。题目中 m 最大到 10^18，所以不能按钱数开数组。

把选择拆成两类

对同一种糖果，如果买两颗，成本一定是：

text

1x_i + y_i

如果买奇数颗，就相当于若干个“两颗组”之外，再多买一颗奇数位糖，额外成本是 x_i。

因此任意方案都可以拆成：

部分	贡献数量	成本	可选次数
两颗组	`2`	`x_i + y_i`	可以无限次
单颗项	`1`	`x_i`	每种糖果最多一次

两颗组可以无限买，所以最优时一定一直使用最便宜的 min(x_i + y_i)。单颗项每种糖果最多选一次，所以如果要选 r 个单颗项，就选最小的 r 个 x_i。

判断能否买到 k 颗

设要买 k 颗。我们枚举单颗项数量 r，它必须满足：

text

1
20 <= r <= min(n, k)
r 和 k 同奇偶

剩下的 k-r 颗必须由两颗组补齐。

若把所有 x_i 排序，记最小的 r 个 x_i 之和为 prefix_x[r]，再记：

text

1p = min(x_i + y_i)

那么固定 r 时的花费为：

text

1prefix_x[r] + (k-r)/2 * p

为了快速求最小值，把式子整理一下。

当 k 为偶数时，r 也为偶数：

text

1cost = k/2 * p + (prefix_x[r] - r/2 * p)

当 k 为奇数时，r 也为奇数：

text

1cost = (k-1)/2 * p + (prefix_x[r] - (r-1)/2 * p)

所以可以预处理：

best_even[t]：在 r <= t 且 r 为偶数时，括号里的最小值；
best_odd[t]：在 r <= t 且 r 为奇数时，括号里的最小值。

这样 check(k) 只要看 k 的奇偶，取 t = min(n,k)，就能 $O(1)$ 算出买 k 颗的最小花费。

二分答案

如果可以买到 k 颗，那么一定也可以买到更少的颗数；如果买不到 k 颗，那么一定买不到更多颗数。

所以答案具有单调性，可以二分最大可行的 k。

实现时注意 m 最大到 10^18，乘法用 __int128 计算，避免溢出。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const long long INF = (long long)4e18;

int n;
long long m;
long long x[MAXN], y[MAXN];
long long sx[MAXN];        // 排序后的 x
long long prefix_x[MAXN];  // 最小的若干个单颗成本之和
long long best_even[MAXN], best_odd[MAXN];
long long min_pair_cost;

void read_input() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
}

void prepare() {
    min_pair_cost = INF;
    for (int i = 1; i <= n; i++) {
        sx[i] = x[i];
        min_pair_cost = min(min_pair_cost, x[i] + y[i]);
    }

    sort(sx + 1, sx + n + 1);
    for (int i = 1; i <= n; i++) {
        prefix_x[i] = prefix_x[i - 1] + sx[i];
    }

    best_even[0] = 0;
    best_odd[0] = INF;
    for (int i = 1; i <= n; i++) {
        best_even[i] = best_even[i - 1];
        best_odd[i] = best_odd[i - 1];

        if (i % 2 == 0) {
            long long value = prefix_x[i] - (long long)(i / 2) * min_pair_cost;
            best_even[i] = min(best_even[i], value);
        } else {
            long long value = prefix_x[i] - (long long)((i - 1) / 2) * min_pair_cost;
            best_odd[i] = min(best_odd[i], value);
        }
    }
}

// 判断是否能用不超过 m 的钱买到 need 颗糖果。
bool check(long long need) {
    int parity = (int)(need % 2);
    int limit = (int)min((long long)n, need);
    long long best_single_part = (parity == 0) ? best_even[limit] : best_odd[limit];

    if (best_single_part >= INF / 2) {
        return false;
    }

    __int128 pair_cnt = (need - parity) / 2;
    __int128 cost = pair_cnt * min_pair_cost + best_single_part;

    return cost <= m;
}

void solve() {
    long long left = 0;
    long long right = m;
    long long ans = 0;

    prepare();

    while (left <= right) {
        long long mid = (left + right) / 2;
        if (check(mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

排序 x_i 需要 $O(n log n)$ 。预处理前缀和、best_even、best_odd 需要 $O(n)$ 。每次 check(k) 是 $O(1)$ ，二分答案需要 $O(log m)$ 次。

总时间复杂度：

text

1O(n log n + log m)

空间复杂度：

text

1O(n)

总结

本题的关键不是按预算做背包，而是重新理解“交替价格”的结构。

同一种糖果每两颗形成一个固定成本的组，所有两颗组中只需要使用最便宜的一种；奇数位多出来的单颗糖，每种糖果最多贡献一次，按 x_i 排序后取前缀即可。

把这两部分拆开后，check(k) 就能快速判断，于是用二分答案求最大糖果数。

P14635 [NOIP2025] 糖果店

题目描述

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

说明/提示

【样例 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 \le n \le 10^5$ ；
$1 \le m \le 10^{18}$ ；
对于所有 $1 \le i \le n$ ，均有 $1 \le x_i, y_i \le 10^9$ 。

::cute-table{tuack}

测试点编号	$n \le$	$m \le$	特殊性质
$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 \le i \le n$ ，均有 $x_i = y_i$ 。

特殊性质 B：对于所有 $1 \le i \le n$ ，均有 $x_i \ge y_i$ 。