[蓝桥杯 2023 省 A] 买瓜

形式化题目

给定 $n$ 个正整数 $A_1, A_2, \dots, A_n$ 和一个目标正整数 $m$ 。对每个 $A_i$ 选择如下三种处理之一：

不买：贡献重量 $0$ ，代价 $0$ ；
劈开只买一半：贡献重量 $\dfrac{A_i}{2}$ ，代价 $1$ ；
买整个：贡献重量 $A_i$ ，代价 $0$ 。

若存在一种选择使贡献重量之和恰好等于 $m$ ，求代价总和的最小值；否则输出 $-1$ 。

建模：把“半个瓜”变成整数

半只瓜的重量可能是小数（ $A_i$ 为奇数时），直接做浮点比较很容易出错。注意到“半个”永远是原重量的一半，而我们只需要判断是否恰好等于 $m$ ，所以可以把所有重量统一乘 $2$ ：

目标由 $m$ 变为 $2m$ ，记 target = 2*m；
买整个贡献 $2A_i$ ，买半个贡献 $A_i$ ，不买贡献 $0$ 。

这样所有涉及的量都是整数，“恰好”退化成整数相等，不必担心精度。

于是题意等价于：每个瓜在 $\{0,\ A_i,\ 2A_i\}$ 中选一个贡献值，其中取 $A_i$ 时额外花费 $1$ 的代价，问凑出 target 的最小总代价。

暴力解法

思路

最直白的做法就是对每个瓜枚举三种去向，把所有 $3^n$ 种组合都试一遍：累加重量、累加劈瓜数，若重量恰好等于 target 就更新答案，最后取最小。 $n \le 12$ 时 $3^{12}\approx 5.3\times 10^5$ ，完全跑得动，足以作为对拍基线。

搜索时加上两个显然的可行性判断：重量超过 target 立即返回（重量都是正的，再加只会更大），劈瓜数已经不小于当前最优答案也返回。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:07
 * update_at: 2026-10-03 11:20
 *
 * P9234 [蓝桥杯 2023 省 A] 买瓜 —— 暴力对拍解
 *
 * 每个瓜枚举三种去向（不买 / 买半个 / 买整个），3^n 穷举所有方案，
 * 取能凑出恰好 m 的方案中最少的劈瓜数。n<=12 时约 5*10^5 种，足够对拍。
 *
 * 同样把重量统一乘 2，半个瓜的重量就是整数，避免浮点误差。
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 35;

int n;
ll m;
ll a[maxn];   // 已乘 2 的重量
ll target;
int best;

// dep: 第几个瓜；sum: 当前重量和（乘 2 后）；cuts: 已劈瓜数
void dfs(int dep, ll sum, int cuts) {
    if (cuts >= best) return;      // 已经不比当前最优更好
    if (dep == n) {
        if (sum == target) best = cuts;
        return;
    }
    if (sum > target) return;      // 重量都是正的，超了就回不去
    dfs(dep + 1, sum, cuts);                        // 不买
    dfs(dep + 1, sum + a[dep], cuts + 1);           // 买半个，劈一刀
    dfs(dep + 1, sum + 2 * a[dep], cuts);           // 买整个
}

int main() {
    scanf("%d %lld", &n, &m);
    target = 2 * m;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    // a[i] 保持原重量：放大后的模型里，半个瓜贡献 a[i]，整个瓜贡献 2*a[i]。
    best = n + 1;
    dfs(0, 0, 0);
    if (best > n) printf("-1\n");
    else printf("%d\n", best);
    return 0;
}

复杂度

时间复杂度 $O(3^n)$ ，空间复杂度 $O(n)$ （递归栈）。

瓶颈

$3^n$ 只适合 $n \le 12$ 左右。题面 $n$ 最大到 $30$ ， $3^{30}$ 是天文数字；即使 $60\%$ 的部分分 $n \le 20$ ， $3^{20} \approx 3.5\times 10^9$ 也过不去。

一种自然的优化是排序后加剪枝（超重、剩余重量上界、劈瓜数不小于当前最优等）。这类剪枝在随机的数据上确实很快，但它没有复杂度保证：当 target 恰好落在总和的一半附近、且组合非常密集时，搜索树依然会爆炸，很容易在若干组数据上超时。我们需要一个有明确上界的方法。

正解：折半搜索

关键观察

枚举的量级是 $3^n$ ，而 $n$ 最大只有 $30$ 。折半搜索（meet in the middle）正是为这种“枚举量随个数指数增长”的情形准备的：把瓜分成两半各自枚举，每半只有 $3^{n/2} \approx 3^{15} \approx 1.4\times 10^7$ 种，然后再把两半的结果合并。

合并的关键是：整份方案由“左半的贡献”和“右半的贡献”拼成，重量和 left + right = target。所以只要把左半所有可达的重量连同“凑出这个重量最少劈几刀”记录下来，枚举右半时用 target - right 去左半查表即可。把左半的状态按重量排序后，每个重量对应的最小劈瓜数可以直接二分取出。

为了让查表更快，把每个状态打包成一个整数 (重量 << 5) | 劈瓜数：劈瓜数最大 $30$ ， $5$ 个二进制位足够，装进低位不影响按重量的大小比较。排序后，同一个重量里劈瓜数小的排在前面，因此二分到的第一个就是该重量对应的最小劈瓜数，去重时也只需保留每个重量的第一条。

思路

排序：把瓜按重量从大到小排序。
全局无解判定（两条，都很廉价）：
- 所有瓜买整只也凑不到 target，输出 $-1$ ；
- 每个瓜的贡献都只能是 $0$ 、 $A_i$ 、 $2A_i$ ，它们都是 $g=\gcd(A_1,\dots,A_n)$ 的倍数，所以总重量必是 $g$ 的倍数。若 target 不是 $g$ 的倍数，一定凑不出，输出 $-1$ 。
取前 half = n/2 个瓜作为左半，递归枚举每个瓜的三种去向，把可达状态打包收集起来。
把左半状态排序，并按重量去重（同重量只留最小劈瓜数）。
枚举右半的每种去向，对每个右半方案用 need = target - 右半重量 在左半里二分查找，若命中就把 右半劈瓜数 + 左半劈瓜数 拿去更新答案。

枚举时同样保留两条正确的剪枝：已选重量超过 target 就返回；以及用“剩下的瓜全买整只”的重量上界判断本侧能否补上另一侧可能需要的缺口。这些剪枝只砍掉确定无解的分支，不影响答案正确性。

代码

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:07
 * update_at: 2026-10-03 11:36
 *
 * P9234 [蓝桥杯 2023 省 A] 买瓜
 *
 * 模型：每个瓜有三种去向
 *   不买          -> 重量贡献 0
 *   劈开只买半个  -> 重量贡献 A_i/2，劈瓜数 +1
 *   买整个        -> 重量贡献 A_i，  劈瓜数不变
 * 要求重量和恰好为 m，最小化劈瓜数。
 *
 * 技巧一：把所有重量统一乘 2，半个瓜的重量就是整数 A_i，整瓜是 2*A_i，
 *         目标变成 target = 2*m，全程整数运算，不丢精度。
 * 技巧二：直接枚举是 3^n（n=30 时约 2*10^14，必然超时），采用折半搜索：
 *         把瓜分成两半分别枚举，左半记录"凑出重量 w 最少要劈几刀"，
 *         右半枚举后用 target-右半重量 去左半里查表，合并答案。
 *         复杂度降到约 2*3^(n/2)，n=30 时约 3*10^7。
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 35;

int n;
ll m;
ll a[maxn];   // 每个瓜的重量（原始值）
ll target;    // 目标重量 = 2*m

int half;              // 前半部分的瓜的个数
ll leftWholeMax;       // 左半全部买整瓜的重量和（放大后）
ll rightWholeMax;      // 右半全部买整瓜的重量和（放大后）

ull *leftPack;         // 左半所有可达状态：打包成 (重量 << 5) | 劈瓜数
long long leftCnt;     // 左半状态数
int ans;               // 最优劈瓜数

// 从大到小排序，让大的瓜先决策，剪枝更早生效
bool cmp_greater(ll x, ll y) {
    return x > y;
}

ll gcd_ll(ll x, ll y) {
    while (y) {
        ll t = x % y;
        x = y;
        y = t;
    }
    return x;
}

// 枚举左半的每一种去向，收集所有可达重量
// idx: 当前瓜；sum: 已选重量（放大后）；cuts: 已劈瓜数
// restWhole: 剩下的左半瓜全部买整瓜的重量和（上界，用于剪枝）
void enumerateLeft(int idx, ll sum, int cuts, ll restWhole) {
    if (sum > target) return;
    // 左半最多把重量补到 sum+restWhole，若这个上界还够不到
    // 右半可能需要的下界，这条分支就没用
    if (sum + restWhole < target - rightWholeMax) return;
    if (idx == half) {
        leftPack[leftCnt++] = ((ull)sum << 5) | (ull)cuts;
        return;
    }
    ll nxt = restWhole - 2 * a[idx];
    enumerateLeft(idx + 1, sum + 2 * a[idx], cuts, nxt);      // 买整个
    enumerateLeft(idx + 1, sum + a[idx], cuts + 1, nxt);      // 买半个，劈一刀
    enumerateLeft(idx + 1, sum, cuts, nxt);                   // 不买
}

// 枚举右半的每一种去向，用 target-sum 去左半查表合并答案
void enumerateRight(int idx, ll sum, int cuts, ll restWhole) {
    if (sum > target) return;
    // 右半全买整瓜也只有 sum+restWhole，若还够不到左半能提供的下界，剪掉
    if (sum + restWhole < target - leftWholeMax) return;
    if (idx == n) {
        ll need = target - sum;
        if (need < 0 || need > leftWholeMax) return;
        // 左半状态按 (重量<<5)|劈瓜数 升序排列，
        // 相同重量时劈瓜数小的排前面，所以首次命中就是最优
        ull key = ((ull)need << 5);
        ull *lo = lower_bound(leftPack, leftPack + leftCnt, key);
        if (lo != leftPack + leftCnt && ((*lo) >> 5) == (ull)need) {
            int c = (int)((*lo) & 31);
            if (cuts + c < ans) ans = cuts + c;
        }
        return;
    }
    ll nxt = restWhole - 2 * a[idx];
    enumerateRight(idx + 1, sum + 2 * a[idx], cuts, nxt);     // 买整个
    enumerateRight(idx + 1, sum + a[idx], cuts + 1, nxt);     // 买半个，劈一刀
    enumerateRight(idx + 1, sum, cuts, nxt);                  // 不买
}

void read_data() {
    scanf("%d %lld", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
}

signed main () {
    read_data();

    sort(a, a + n, cmp_greater);
    target = 2 * m;

    // 剪枝 1：全部买整瓜也够不到目标，必然无解
    ll total = 0;
    for (int i = 0; i < n; i++) total += 2 * a[i];
    if (target > total) {
        printf("-1\n");
        return 0;
    }

    // 剪枝 2：每个瓜贡献的重量都是 g = gcd(A_1..A_n) 的倍数，
    // 所以 total 必为 g 的倍数。target 不是 g 的倍数时一定凑不出来，
    // 例如 30 个 10^9 的瓜凑不出 10^9 + 1。
    ll g = 0;
    for (int i = 0; i < n; i++) g = gcd_ll(g, a[i]);
    if (g && target % g != 0) {
        printf("-1\n");
        return 0;
    }

    half = n / 2;
    leftWholeMax = 0;
    for (int i = 0; i < half; i++) leftWholeMax += 2 * a[i];
    rightWholeMax = 0;
    for (int i = half; i < n; i++) rightWholeMax += 2 * a[i];

    // 左半最多 3^half 种去向；half = n/2 <= 15，约 1.4*10^7 个状态
    long long cap = 1;
    for (int i = 0; i < half; i++) cap *= 3;
    leftPack = new ull[cap + 5];
    leftCnt = 0;
    enumerateLeft(0, 0, 0, leftWholeMax);

    sort(leftPack, leftPack + leftCnt);
    // 同一重量只保留最小劈瓜数：打包后劈瓜数在低位，升序排序后
    // 相同重量里第一个出现的就是劈瓜数最小的，后面的直接丢掉
    long long w = 0;
    for (long long i = 0; i < leftCnt; i++) {
        if (i > 0 && (leftPack[i] >> 5) == (leftPack[i - 1] >> 5)) continue;
        leftPack[w++] = leftPack[i];
    }
    leftCnt = w;

    ans = n + 1;   // n+1 表示"还没找到可行方案"
    enumerateRight(half, 0, 0, rightWholeMax);

    if (ans > n) printf("-1\n");
    else printf("%d\n", ans);

    return 0;
}

复杂度

设 half = n/2。左半枚举约 $3^{half}$ 个状态，排序与去重为 $O(3^{half}\log 3^{half})$ ；右半枚举 $3^{n-half}$ 个状态，每个状态一次二分查找。

当 $n = 30$ 时， $3^{15}\approx 1.4\times 10^7$ ，总运算量约几千万级别，可以在时限内跑完。空间上存放左半状态需要约 $1.4\times 10^7$ 个 unsigned long long，约 $110$ MB。

总结

这道题的难点不在算法本身，而在于怎么把题意干净地转成搜索模型、以及怎么让搜索活下来：

模型转化：把“不买 / 劈开买一半 / 买整个”看成三选一的贡献值，并把所有重量乘 $2$ ，把半只瓜这个小数量变成整数，避免浮点比较。
为什么不是剪枝暴搜：n \le 30 时 $3^{30}$ 大到无法接受，单纯加剪枝在 target 接近总和一半的数据上仍会退化成天文数字，没有复杂度保证。
折半搜索：把 $3^n$ 拆成两半各 $3^{n/2}$ ，左半建表（重量 → 最小劈瓜数），右半枚举时二分查表合并，把复杂度降到约 $2\times 3^{n/2}$ 。
打包与排序：把 (重量, 劈瓜数) 打包成一个整数，使二分一次就能同时取出“重量恰好为 need 且劈瓜数最小”的记录。

值得记住的是：当题目形如“ $n$ 不大、每个物品只有几种离散选择、要求恰好凑成某个量”时，正解往往就是折半搜索；本题重量高达 $10^9$ ，背包类 DP 无法开下那么大的状态，也进一步说明了为什么必须走搜索路线。