[NOIP2025] 清仓甩卖

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

按原价降序刻画贪心失败的关键交换对，用组合数统计坏定价方案后从 2^n 中扣除。

OJ: luogu

题目 ID: P14636

难度:提高+/省选-

标签:贪心组合计数排序

日期: 2026-06-22 17:57

题意

有 n 颗糖果，第 i 颗糖果原价为 a_i。每颗糖果的清仓价可以独立定成 1 元或 2 元。

定价方案确定后，小 R 会把糖果按性价比 a_i / w_i 从大到小排序；性价比相同则原价高的先买，仍相同则编号小的先买。然后他按这个顺序扫描，钱够就买，否则跳过。

题目要求统计：在所有 2^n 种定价方案里，有多少种方案使得小 R 按这个贪心策略买到的原价总和，等于预算 m 下能买到的最大原价总和。答案对 998244353 取模。

输入第一行的第一个整数是测试点编号，可以读入但不用。

思路

先看一个能直接验证定义的暴力做法：枚举每种定价方案，模拟小 R 的性价比贪心，再用 0/1 背包求同一方案下真正的最优原价和，比较二者是否相等。

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
95
96
97
98
99
100
101// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;
const int MOD = 998244353;

int control_id, test_count;
int n, m;
long long a[MAXN];
int w[MAXN];

bool cmp_item(int x, int y) {
    long long left = a[x] * w[y];
    long long right = a[y] * w[x];
    if (left != right) {
        return left > right;
    }
    if (a[x] != a[y]) {
        return a[x] > a[y];
    }
    return x < y;
}

long long greedy_value() {
    vector<int> id;
    for (int i = 1; i <= n; i++) {
        id.push_back(i);
    }
    sort(id.begin(), id.end(), cmp_item);

    int money = m;
    long long sum = 0;
    for (int i = 0; i < (int)id.size(); i++) {
        int x = id[i];
        if (money >= w[x]) {
            money -= w[x];
            sum += a[x];
        }
    }
    return sum;
}

long long optimal_value() {
    vector<long long> dp(m + 1, -1);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int money = m; money >= w[i]; money--) {
            if (dp[money - w[i]] < 0) {
                continue;
            }
            dp[money] = max(dp[money], dp[money - w[i]] + a[i]);
        }
    }

    long long best = 0;
    for (int money = 0; money <= m; money++) {
        best = max(best, dp[money]);
    }
    return best;
}

void solve_one() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    long long ans = 0;
    int total = 1 << n;

    // 枚举每颗糖果定价为 1 或 2 元。
    for (int mask = 0; mask < total; mask++) {
        for (int i = 1; i <= n; i++) {
            if (mask & (1 << (i - 1))) {
                w[i] = 2;
            } else {
                w[i] = 1;
            }
        }

        if (greedy_value() == optimal_value()) {
            ans++;
        }
    }

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

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

    cin >> control_id >> test_count;
    while (test_count--) {
        solve_one();
    }

    return 0;
}

这个做法的瓶颈很明显：定价方案有 2^n 种，而 n 最大是 5000。所以我们反过来统计“不合法”的定价方案。

先把糖果按原价从大到小排序：

text

1a_1 >= a_2 >= ... >= a_n

如果一个定价方案不合法，说明贪心买到的集合不是最优集合。由于清仓价格只有 1 和 2，一次最关键的失败可以看成：

有一颗原价更高的糖果 i，它被定价为 2 元；
有一颗原价更低的糖果 j，它被定价为 1 元；
糖果 j 在贪心顺序里排在糖果 i 前面，并且被买走；
到贪心考虑糖果 i 时，剩余钱已经不足 2 元；
把 j 换成 i 后，原价总和会变大。

这里必须有 a_i > a_j，否则交换不会让答案变大。还必须有：

text

1a_j / 1 > a_i / 2

也就是：

text

12a_j > a_i

否则 j 不会排在 i 前面，也挡不住它。

接下来固定这对关键糖果 (i, j)。糖果 j 是一个已经买走的 1 元糖果，糖果 i 是被漏掉的 2 元糖果。为了让贪心考虑 i 时剩余钱少于 2，前面必须已经花掉至少 m - 1 元。

在这个关键结构里，除了糖果 j 之外，还需要从 j 前面的糖果里选出：

text

1m - i - 1

个会被贪心买走的 1 元糖果。可选位置有 j - 2 个，因此贡献：

text

1C(j - 2, m - i - 1)

还剩一类自由选择：如果某个后缀糖果 k 满足：

text

1a_k + a_j < a_i

那么它无论定成 1 还是 2，都不会改变由 (i,j) 定位的这次关键失败。设满足条件的后缀起点为 p，这部分贡献：

text

12^(n - p + 1)

于是每个关键对 (i,j) 对坏方案数的贡献为：

text

1C(j - 2, m - i - 1) * 2^(n - p + 1)

枚举所有合法的 (i,j)，累加坏方案数 bad，最后答案就是：

text

12^n - bad

实现时预处理组合数 C(i,j) 和 2^i。内层枚举 j 时，用指针 p 维护满足 a[p] + a[j] < a[i] 的后缀起点。组合数参数不合法时直接视为 0。

代码

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 = 5005;
const int MOD = 998244353;

int control_id, test_count;
int n, m;
long long a[MAXN];
int comb[MAXN][MAXN]; // comb[i][j] = C(i, j)
int pow2[MAXN];       // pow2[i] = 2^i

void prepare() {
    pow2[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        pow2[i] = pow2[i - 1] * 2LL % MOD;
    }

    comb[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        comb[i][0] = comb[i][i] = 1;
        for (int j = 1; j < i; j++) {
            comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
            if (comb[i][j] >= MOD) {
                comb[i][j] -= MOD;
            }
        }
    }
}

int get_comb(int x, int y) {
    if (x < 0 || y < 0 || y > x) {
        return 0;
    }
    return comb[x][y];
}

void solve_one() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    sort(a + 1, a + n + 1, greater<long long>());

    long long bad = 0;

    // 枚举最优解会买的 2 元糖果 i，以及贪心会用来卡住它的 1 元糖果 j。
    for (int i = 1; i <= n; i++) {
        int need_extra = m - i - 1;
        if (need_extra < 0) {
            break;
        }

        int p = n + 1;
        int start_j = max(i + 1, m - i + 1);

        for (int j = start_j; j <= n; j++) {
            if (a[i] == a[j]) {
                continue;
            }
            if (a[i] >= 2LL * a[j]) {
                break;
            }

            // p 是最靠前的位置，使得 [p, n] 的糖果都能作为“较低性价比的 1 元糖果”。
            while (p > 1 && a[p - 1] + a[j] < a[i]) {
                p--;
            }

            bad += 1LL * get_comb(j - 2, need_extra) * pow2[n - p + 1] % MOD;
            if (bad >= MOD) {
                bad -= MOD;
            }
        }
    }

    int ans = (pow2[n] - (int)(bad % MOD) + MOD) % MOD;
    cout << ans << '\n';
}

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

    prepare();

    cin >> control_id >> test_count;
    while (test_count--) {
        solve_one();
    }

    return 0;
}

复杂度

预处理组合数的时间复杂度为 $O(MAXN^2)$ ，空间复杂度为 $O(MAXN^2)$ 。

每组数据排序复杂度为 $O(n log n)$ ，枚举关键对的复杂度为 $O(n^2)$ 。额外空间为 $O(n)$ 。

总结

这题的关键不是模拟小 R 的贪心，而是找出贪心失败的最小结构：一个被买走的 1 元低原价糖果，挡住了一颗更高原价的 2 元糖果。

找到这个结构后，题目就变成了组合计数：固定关键对 (i,j)，前面选多少个 1 元糖果由组合数统计，后缀中不会影响关键失败的糖果用二次幂统计。最后用总方案数减去坏方案数即可。

P14636 [NOIP2025] 清仓甩卖

题目背景

额外提供了 0.5 秒的时限。

题目描述

小 X 的糖果促销策略很成功，现在糖果店只剩下了 $n$ 颗糖果，其中第 $i$ ( $1 \le i \le n$ ) 颗糖果的原价为 $a_i$ 元。小 X 计划将它们全部重新定价，清仓甩卖。具体地，小 X 会将每颗糖果的清仓价格分别定为 $1$ 元或 $2$ 元。设第 $i$ ( $1 \le i \le n$ ) 颗糖果的清仓价格为 $w_i \in \{1,2\}$ 元，则它的性价比被定义为原价与清仓价格的比值，即 $\frac{a_i}{w_i}$ 。

小 R 又带了 $m$ 元钱买糖果。这一次，小 R 希望他购买到的糖果的原价总和最大，于是他采用了以下购买策略：将所有糖果按照性价比从大到小排序，然后依次考虑每一颗糖果。具体地，若小 R 在考虑第 $i$ ( $1 \le i \le n$ ) 颗糖果时剩余的钱至少为 $w_i$ 元，则他会购买这颗糖果；否则他会跳过这颗糖果，继续考虑下一颗。特别地，若存在两颗糖果的性价比相同，则小 R 会先考虑原价较高的糖果；若存在两颗糖果的性价比与原价均相同，则小 R 会先考虑编号较小的糖果。

例如，若小 X 的糖果商店剩余 $3$ 颗糖果，原价分别为 $a_1=1$ ， $a_2=3$ ， $a_3=5$ ，而清仓价格分别为 $w_1=w_2=1$ ， $w_3=2$ ，则性价比分别为 $1, 3, \frac{5}{2}$ 。因此小 R 会先考虑第 $2$ 颗糖果，然后考虑第 $3$ 颗糖果，最后考虑第 $1$ 颗糖果。

小 R 想知道，在小 X 的所有 $2^n$ 种定价方案中，有多少种定价方案使得他按照上述购买策略能购买到的糖果的原价总和最大。你需要帮助小 R 求出满足要求的定价方案的数量。由于答案可能较大，你只需要求出答案对 $998,244,353$ 取模后的结果。

输入格式

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c, t$ ，分别表示测试点编号与测试数据组数。 $c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含两个正整数 $n, m$ ，分别表示糖果的数量与小 R 的钱数；
第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ ，分别表示每颗糖果的原价。

输出格式

对于每组测试数据，输出一行一个非负整数，表示使得小 R 购买到的糖果的原价总和达到最大值的定价方案数对 $998,244,353$ 取模后的结果。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

【样例 1 解释】

该样例即为【题目描述】中的例子。共有以下 $6$ 种定价方案使得小 R 购买到的糖果原价总和最大，分别为：

$w_1 = w_2 = w_3 = 1$ ，小 R 购买到的糖果原价总和为 $8$ ；
$w_1 = w_3 = 1$ ， $w_2 = 2$ ，小 R 购买到的糖果原价总和为 $6$ ；
$w_1 = 1$ ， $w_2 = w_3 = 2$ ，小 R 购买到的糖果原价总和为 $5$ ；
$w_2 = w_3 = 1$ ， $w_1 = 2$ ，小 R 购买到的糖果原价总和为 $8$ ；
$w_3 = 1$ ， $w_1 = w_2 = 2$ ，小 R 购买到的糖果原价总和为 $5$ ；
$w_1 = w_2 = w_3 = 2$ ，小 R 购买到的糖果原价总和为 $5$ 。

注意：若 $w_1 = w_2 = 1$ ， $w_3 = 2$ ，则小 R 会依次购买第 $2$ 颗和第 $1$ 颗糖果，原价总和为 $4$ ，但小 R 可以只购买第 $3$ 颗糖果，原价总和为 $5$ 。因此该定价方案无法使小 R 购买到的糖果的原价总和达到最大值。

【样例 2】

见选手目录下的 sale/sale2.in 与 sale/sale2.ans。

该样例满足测试点 $1 \sim 3$ 的约束条件。

【样例 3】

见选手目录下的 sale/sale3.in 与 sale/sale3.ans。

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

【样例 4】

见选手目录下的 sale/sale4.in 与 sale/sale4.ans。

该样例满足测试点 $7 \sim 9$ 的约束条件。

【样例 5】

见选手目录下的 sale/sale5.in 与 sale/sale5.ans。

该样例满足测试点 $10 \sim 12$ 的约束条件。

【样例 6】

见选手目录下的 sale/sale6.in 与 sale/sale6.ans。

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

【样例 7】

见选手目录下的 sale/sale7.in 与 sale/sale7.ans。

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

【样例 8】

见选手目录下的 sale/sale8.in 与 sale/sale8.ans。

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

【样例 9】

见选手目录下的 sale/sale9.in 与 sale/sale9.ans。

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

【样例 10】

见选手目录下的 sale/sale10.in 与 sale/sale10.ans。

该样例满足测试点 $21 \sim 23$ 的约束条件。

【样例 11】

见选手目录下的 sale/sale11.in 与 sale/sale11.ans。

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

【数据范围】

设 $N$ 为单个测试点内所有测试数据的 $n$ 的和。对于所有测试数据，均有：

$1 \le t \le 5 \times 10^4$ ；
$1 \le n \le 5,000$ ， $N \le 5 \times 10^4$ ， $1 \le m \le 2n - 1$ ；
对于所有 $1 \le i \le n$ ，均有 $1 \le a_i \le 10^9$ 。

::cute-table{tuack}

测试点编号	$n \le$	$N \le$	$m$	特殊性质
$1\sim 3$	$5$	$5{,}000$	$\le 2n - 1$	无
$4,5$	$10$	^	^	^
$6$	$40$	^	^	^
$7\sim 9$	$300$	^	$=2$	^
$10\sim 12$	^	^	$\le 2n - 1$	B
$13$	^	^	^	无
$14,15$	$10^3$	$10^4$	$=2$	^
$16$	^	^	$=2n - 1$	^
$17$	^	^	$=2n - 2$	^
$18$	^	^	$\le 2n - 1$	A
$19,20$	^	^	^	B
$21\sim 23$	^	^	^	无
$24,25$	$5{,}000$	$5 \times 10^4$	^	^

特殊性质 A： $a_1 = a_2 = \cdots = a_n$ 。

特殊性质 B：对于所有 $1 \le i \le n$ ，均有 $a_i > 5 \times 10^8$ 。