不使用折半搜索A这道题

祝你们成功（滑稽

笑点：$n\le 30$，$O(3^n)$ 能过且单测试点 <3ms，$O(3^{n/2})$ 卡得很满，单测试点 <730ms。

$O(3^n)$ 爆搜代码

https://www.luogu.com.cn/record/172447789

#include <iostream>
#include <algorithm>

using std::cin;
typedef long long ll;
constexpr int N=32;

int n,m,ans;

ll suf[N],a[N],b[N];

// 显然是 O(3^n)
void dfs(int i=1,ll sum=0,int cnt=0)
{
	if(cnt>=ans)return; // 劣于当前答案，退出
	if(sum==m)return ans=std::min(cnt,ans),void(); // 到达目标状态，更新答案
	if(sum>m||sum+suf[i]<m||i>n)return; // 剪枝
	dfs(i+1,sum,cnt); // 不取
	dfs(i+1,sum+a[i],cnt); // 取整个
	dfs(i+1,sum+a[i]/2,cnt+1); // 劈完取半个
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;m<<=1;
	ans=114514;
	for(int i=1;i<=n;i++)cin>>a[i],a[i]<<=1;
	std::sort(a+1,a+n+1,std::greater<ll>()); // 从大到小排序，非常重要的优化！！！
	for(int i=n;i;i--)suf[i]=suf[i+1]+a[i]; // 后缀和
	dfs(); // 爆搜
	if(ans>n)puts("-1");
	else printf("%d",ans);
	return 0;
}

$O(3^{n/2})$ 折半搜索题解（看长度就知道有多难搞）。

问题

1. 为什么暴力能过？或者说，代码中的排序起到了什么神秘作用？
2. 如果能卡，如何卡掉暴力做法？是否应该添加 hack 数据？毕竟是道蓝题。

求解答。悬关。