难度 | 算法s | 日期 | 题目链接 |
---|---|---|---|
普及+/提高 | 折半搜索、剪枝 | 2025-07-20 | https://luogu.com.cn/problem/P9234 |
我觉得此题没有参考价值。
P9234 [蓝桥杯 2023 省 A] 买瓜
本题解聚焦于剪枝优化上。如果只是简单地使用折半搜索,很容易 \(\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
多。
肯定是题目数据太水了!!而且还有奇妙的性质?