本文主要是介绍蓝桥杯2023年省A（一波三折的）【买瓜】折半搜索+剪枝+排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：洛谷 P9234 [蓝桥杯 2023 省 A] 买瓜
折半搜索
一开始觉得像dp，试着写了，显然过不了，但我实在觉得搜索也过不了啊，去看题解，发现使用了折半搜索（每天都觉得啥都不会捏
折半搜索就是先搜一半，记录下答案，再搜一半，最后把答案整合在一起
比如这题，每个数有三种选法，复杂度3n，折半后就是2*3n/2，大大降低了
但是这个复杂度还是过不了，后面就是不停优化剪枝
剪枝
剪枝1
当前和已经超过m (sum > m)
剪枝2
当前劈瓜次数已经超过历史最优 (k >= ans)
剪枝3
达到同样的和，曾经有过劈瓜数更小的方案 (mp.count(sum) && mp[sum] < k)
折半+剪枝（76分）
用unordered_map更快
#include <vector>
#include <iostream>
#include <cstdio>
#include <map>
#include <unordered_map>
#include <ctime>
using namespace std;typedef long long ll;
const int N = 35;ll a[N];
int ans = N;
unordered_map<ll, int> mp;//unordered_map更快
ll n, m;void dfs1(int i, int k, ll sum)
{if (sum > m) return;//超了，剪if (k >= ans) return;if (sum == m)//到了，走了{ans = min(ans, k);return; }if (mp.count(sum) && mp[sum] < k) return;//有过更优情况，剪！if (i > n / 2)//到头了，把搜到的东西记一下{//用map记录达到sum的砍刀数最小值if (mp.count(sum)) mp[sum] = min(mp[sum], k);else mp[sum] = k;return;}//先搜贡献大的更容易找到答案（大概吧dfs1(i + 1, k, sum + a[i] + a[i]);//整个dfs1(i + 1, k + 1, sum + a[i]);//半个dfs1(i + 1, k, sum); //不要
}void dfs2(int i, int k, ll sum)
{if (sum > m) return;if (k >= ans) return;if (sum == m){ans = min(ans, k);return; }if (i > n){//如果另一半有匹配的就更新答案if (mp.count(m - sum)) ans = min(ans, k + mp[m - sum]);return;}dfs2(i + 1, k, sum + a[i] + a[i]);dfs2(i + 1, k + 1, sum + a[i]);dfs2(i + 1, k, sum);
}
int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;m += m;//为了不出现小数，把a[i]当半个瓜用，那么m也要翻倍for (int i = 1; i <= n; i++){cin >> a[i];}dfs1(1, 0, 0);dfs2(n/2+1, 0, 0);if (ans == N) cout << -1;else cout << ans;return 0;
}
继续看题解，发现很重要的一点是要给数组排序
为什么呢，不知道，大家都不说
好像挺有道理的但是我说不出道理，先放着
加上sort之后A了
觉得自己无敌了吧？来看看这个
题目 3145: 蓝桥杯2023年第十四届省赛真题-买瓜
欸~一模一样的代码只有82分
最后是怎么过的呢，要把数组从大到小排序
为什么呢
我的理解是，在搜第二段的时候，前面已经出现很多凑到m的情况，使ans变小了，所以第二段会被剪得更狠；相比之下第一段则几乎都要搜到头，所以重点在于要把第一段剪了。那有没有办法让第一段多剪掉一点呢，就让第一段都是大数，sum容易超过m，就会多多被剪了
加上从大到小排序：
sort(a + 1, a + n + 1, greater<int>());
正当我欢天喜地地准备结束这题的时候，我手欠地把从大到小版交到了洛谷
嘿——您猜怎么着？TLE了！
好吧我前边都是一顿瞎说（但我真是觉得有道理啊）
那只能是数据问题了，但是数据问题要怎么A啊！
剪枝4
后面我又翻看题解，发现了一个新的剪枝：
预处理后缀和，当前sum加上后缀和也够不到m的话就直接剪
注意这个剪枝只能在第一段中使用，因为第二段本身就要匹配第一段的答案，没法判断会不会不够
void dfs1(int i, int k, ll sum)
{if (sum > m) return;if (k >= ans) return;if (sum + suf[i] < m) return;//注意第i个还没加过，所以是判断sum + suf[i]if (sum == m){ans = min(ans, k);return; }if (i > n / 2){if (mp.count(sum)) mp[sum] = min(mp[sum], k);else mp[sum] = k;return;}dfs1(i + 1, k, sum + a[i] + a[i]);dfs1(i + 1, k + 1, sum + a[i]);dfs1(i + 1, k, sum);
}
还有个注意点，要sort之后再算后缀和（对就是我这么傻
以及因为我存的a[i]算半个瓜，算后缀和要算整个瓜，所以要加两次
sort(a + 1, a + n + 1, greater<int>()); suf[n + 1] = 0;for (int i = n; i >= 1; i--){suf[i] = suf[i + 1] + a[i] + a[i];}
贴一个两边都能A的代码
#include <vector>
#include <iostream>
#include <cstdio>
#include <map>
#include <unordered_map>
#include <ctime>
#include <algorithm>
using namespace std;typedef long long ll;
const int N = 35;ll a[N], suf[N];
int ans = N;
unordered_map<ll, int> mp;
ll n, m;void dfs1(int i, int k, ll sum)
{if (sum > m) return;//超了，剪if (k >= ans) return;if (sum + suf[i] < m) return;//注意第i个还没加过，所以是判断sum + suf[i]if (sum == m)//到了，走了{ans = min(ans, k);return; }if (mp.count(sum) && mp[sum] < k) return;//有过更优情况，剪！if (i > n / 2)//到头了，把搜到的东西记一下{//用map记录达到sum的劈瓜数最小值if (mp.count(sum)) mp[sum] = min(mp[sum], k);else mp[sum] = k;return;}//先搜贡献大的更容易找到答案（大概吧dfs1(i + 1, k, sum + a[i] + a[i]);//整个dfs1(i + 1, k + 1, sum + a[i]);//半个dfs1(i + 1, k, sum); //不要
}void dfs2(int i, int k, ll sum)
{if (sum > m) return;if (k >= ans) return;if (sum == m){ans = min(ans, k);return; }if (i > n){//如果另一半有匹配的就更新答案if (mp.count(m - sum)) ans = min(ans, k + mp[m - sum]);return;}dfs2(i + 1, k, sum + a[i] + a[i]);dfs2(i + 1, k + 1, sum + a[i]);dfs2(i + 1, k, sum);
}
int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;m += m;//为了不出现小数，把a[i]当半个瓜用，那么m也要翻倍for (int i = 1; i <= n; i++){cin >> a[i];}//sort(a + 1, a + n + 1); sort(a + 1, a + n + 1, greater<int>()); suf[n + 1] = 0;for (int i = n; i >= 1; i--){suf[i] = suf[i + 1] + a[i] + a[i];}dfs1(1, 0, 0);dfs2(n/2+1, 0, 0);if (ans == N) cout << -1;else cout << ans;return 0;
}
结果就是加上这个剪枝从大到小排序洛谷能过了，但是从小到大c语言网不行，继续看！
其他优化
我就不写了感觉好麻烦要把之前写的推翻重来orz
二分
不直接搜i+1，而是根据还需要的斤数在剩下的瓜里二分（因为已经排序了嘛），大于还需要的斤数的瓜可以不用考虑
（这样二分甚至可以不用折半搜索
见 P9234 [蓝桥杯 2023 省 A] 买瓜 题解
手写哈希表
大概是因为unordered_map还是常数大了吧（
见 买瓜 题解
参考
P9234 [蓝桥杯 2023 省 A] 买瓜 题解
买瓜 题解
买瓜题解
菜死我算了，真在赛场上碰到这种题我就拿个30分吧（默哀
这篇关于蓝桥杯2023年省A（一波三折的）【买瓜】折半搜索+剪枝+排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
