P9234 [蓝桥杯 2023 省 A] 买瓜

难度	算法s	日期	题目链接
普及+/提高	折半搜索、剪枝	2025-07-20	https://luogu.com.cn/problem/P9234

我觉得此题没有参考价值。

本题解聚焦于剪枝优化上。如果只是简单地使用折半搜索，很容易 \(\text{TLE}\)。我感觉这道题的难度在于怎么调优（而不是想到折半搜索）。

以下都把第 \(i\) 个瓜的重量存在 a[i] 中（\(1\le i\le n\)）；n 是瓜的数量，m 是目标重量。

Part I：折半搜索

先说说朴素的搜索方式，让我们结合代码理解一下搜索过程。我们从第一个瓜开始暴力枚举它的三种状态：买、买一半、全买。

// i 表示当前枚举的瓜；sum 表示目前买下的瓜的总重；div 表示到目前一共砍了几刀
void dfs(int i, int sum, int div) {if (i == n + 1) { // 搜到头了if (sum == m) ans = min(ans, div); // 统计答案}// 枚举第 i+1 个瓜的状态dfs(i + 1, sum, div); // 不买第 i 个瓜dfs(i + 1, sum + a[i], div); // 买下整个第 i 个瓜dfs(i + 1, sum + (a[i] >> 1), div + 1); // 买下第 i 个瓜的一半，要让 div +1// a[i] >> 1 相当于 a[i] / 2
}

入口点是 dfs(1, 0, 0)。这样做的时间复杂度如何？不难看出是 \(O(3^n)\)。这题 \(n\le30\)，\(3^{30}\approx10^{14}\)，显然过不了。所以我们要用 折半搜索：

• 令 mid = n / 2，我们先搜第 i ~ mid 个瓜，再搜第 mid+1 ~ n 个瓜。第一遍搜索记为 dfs1()，第二遍是 dfs2()。
• 在 dfs1() 中，每次我们搜完前半段，就记录下 “要买下总重 sum 的瓜，至少要切几刀”。我们创建一个 unordered_map<int,int> mp，mp[sum] 就记录买下总重为sum 的瓜至少要切几刀。
• 在 dfs2() 中，如果我们发现当前 mp[] 中存在 map[m - sum]，那么意味着我们可以在前 n / 2 个瓜中购买总重为 m - sum 的瓜，然后和当前状态 sum，拼起来，恰好达到了目标 m。此时更新答案。

这里要注意一个细节：“砍半” 要把瓜的重量除以 2，可能出现小数，不好处理。所以我们在输入时让目标 m 和每个 a[i] 都乘以 2，这样可以保持问题等价，又可以避免搜索时出现小数。

这样做的时间复杂度如何？搜索每个半段需要枚举 \(O(3^{n/2})\) 种情况，unordered_map 的插入和查询近乎 \(O(1)\)，所以总时间复杂度为：\(O(3^{n/2})\)。

然而请看这里：评测记录 & 代码。\(\text{TLE}\)，\(64\text{pts}\)。接下来，踏上剪枝之旅吧。

Part II：剪枝（效果不大）

我们容易想到以下几种剪枝：

逻辑	说明
if (sum > m) return;	可行性剪枝。如果当前买的瓜已经超过目标了，继续搜索不可能达到目标。
dfs2() 中：if (div >= ans) return;	最优性剪枝。如果当前砍的次数已经超过统计出的最优答案了，继续搜索不可能得到更优解。

应用了以上剪枝，结果请看：评测记录 & 代码。\(\text{TLE}\)，\(76\text{pts}\)。当然，还可以想到下面的几种剪枝（看了一下题解区）：

逻辑	说明
dfs1() 中：if (sum == m) { ans = min(ans, div); return; }	提前统计答案并终止搜索。这样还可以在 dfs1() 中使用上面的最优性剪枝。
dfs1() 中：如果存在 mp[sum] < div，直接 return;	最优性剪枝。正确性有待证明。

但是当你一一尝试这些剪枝后，会发现即使全部打上也难逃 \(\text{TLE}\) 的命运。是时候试试更激进的优化方法了：

Part III：排序（玄学调优）

你可能在讨论区和题解区发现了这个神奇的事情：只要在搜索之前加上一句 sort()，把瓜的大小从小到大排序，就可以神奇地 \(\text{AC}\)。甚至即使你没有用 Part II 提到的任何剪枝！看这里：评测记录 & 代码（没开 O2 哦）。更离谱的是似乎不用折半搜索也能过：排序为什么会使搜索变快 - 洛谷。可见搜之前排序是重要的优化方法。

实在是玄学至极。在洛谷的评测机上，排序后可以带来巨大的性能提升。但是我在本地难以复现这一行为。事实上我构造的数据平均要跑 3s 多。

肯定是题目数据太水了！！而且还有奇妙的性质？