当前位置: 首页 > news >正文

P9234 [蓝桥杯 2023 省 A] 买瓜

难度 算法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> mpmp[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 多。

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

http://www.hskmm.com/?act=detail&tid=25213

相关文章:

  • P1044 [NOIP 2003 普及组] 栈
  • P1080 [NOIP 2012 提高组] 国王游戏
  • 音响没声音
  • P1654 OSU!
  • DynamoDB十年演进:云原生数据库的技术革新
  • 完整教程:MySQL全量、增量备份与恢复
  • 10/5
  • 10/4
  • 嵌入式MCU
  • porting perf性能观测工具
  • Windows常用快捷指令
  • Python 在金融中的应用- Part 1 - 教程
  • QBXT2025S刷题 Day4
  • java学习日记9.25
  • porting 开源memtester
  • 计算机的组成
  • 完整教程:用mediamtx搭建简易rtmp,rtsp视频服务器
  • oppoR9m MTK 6755 开启VCOM的9008模式
  • 关于电脑息屏后自动亮屏的的原因排查及解决方式
  • 机器人世界杯工业联赛技术解析
  • Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2) A~E
  • k8s之基础概念
  • 251005
  • Java基础 Day26 - 详解
  • 14_mklink创建符号链接
  • 7_如何构建知识图谱
  • 点双连通分量例题:矿场搭建
  • MTK oppoR9m Smart Phone flash Tool 提示 ERROR: STATUS_UNSUPPORT_CTRL_CODE (0xC0010004)
  • 我开发的 Chrome 插件 SEO Tools Extension 今天上线了
  • Windows Server部署Vue3+Spring Boot项目 - 实践