[折半搜索] 世界冰球锦标赛（CEOI2015 Day2）

问题描述

今年的世界冰球锦标赛在捷克举行。$Bobek$ 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。

给出 $Bobek$ 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

输入格式

第一行，两个正整数 $N$ 和 $M$，表示比赛的个数和 $Bobek$ 的财产。
第二行，$N$ 个以空格分隔的正整数 $a_i$，代表每场比赛门票的价格。

输出格式

输出一行，表示方案的个数。

样例

样例输入1：

5 1000
100 1500 500 500 1000

样例输出1:

8

样例1解释:
八种方案分别是：

• 一场都不看，溜了溜了。
• 价格 $100$ 的比赛。
• 第一场价格 $500$ 的比赛。
• 第二场价格 $500$ 的比赛。
• 价格 $100$ 的比赛和第一场价格 $500$ 的比赛。
• 价格 $100$ 的比赛和第二场价格 $500$ 的比赛。
• 两场价格 $500$ 的比赛。
• 价格 $1000$ 的比赛。

数据范围

对于 $100\%$ 的数据，$N\le 40$，$M\le 10^{18}$，$a_i\le 10^{16}$。

数据组号	$1\sim 2$	$3\sim 4$	$5\sim 7$	$8\sim 10$
$N\le$	$10$	$20$	$40$	$40$
$M\le$	$10^6$	$10^{18}$	$10^6$	$10^{18}$

题解

首先想到直接搜索，枚举每场比赛是否选择，复杂度为 $\Theta (2^n)$，会超时。

考虑使用折半进行优化，先搜前一半，依然枚举每场比赛是否选择，将搜到的价值记录在数组里。
接下来搜另一半，枚举出价值 $x$，在记录的数组中进行二分 $m-x$，得到可以看到的价值个数，累加即可。
复杂度为 $\Theta (2^{n/2+1})$。

int n, m;
int a[50];
int len = 0, t[1000010];
//第一次搜索
void dfs(int x, int y, int sum){
if(sum > m){
return;
}
if(x > y){
t[++ len] = sum;//记录 sum
return;
}
dfs(x + 1, y, sum);//不选
dfs(x + 1, y, sum + a[x]);//选
}
long long ans = 0;
//第二次搜索
void dfs2(int x, int y, int sum){
if(x > y){
//二分位置
int l = 1, r = len, s = 0;
while(l <= r){
int mid = (l + r) >> 1;
if(t[mid] + sum <= m){
s = mid;
l = mid + 1;
}
else{
r = mid - 1;
}
}
ans += s;//累加
return;
}
dfs2(x + 1, y, sum);
dfs2(x + 1, y, sum + a[x]);
}
int main(){
输入
dfs();
将 t 排序
dfs2();
}

原文地址：https://blog.csdn.net/m0_64542522/article/details/143735850

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！