P4799 【[CEOI2015 Day2]世界冰球锦标赛】 (折半搜索)
part1 40points
暴力的40分是很好写的,直接搜就行
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define int long long
using namespace std;
const int maxn=1e6;
int n,m;
int a[maxn];
int ans=1;
void dfs(int x,int la){
if(la-a[x]<0){
return ;
}
ans++;
for(int i=x+1;i<=n;i++){
dfs(i,la-a[x]);
}
return ;
}
signed main(){
// ios::sync_with_stdio(false);
// freopen("a.in","r",stdin);
cin>>n;
cin>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
dfs(i,m);
}
cout<<ans;
return 0;
}
pasrt2 100points
我们来考虑100分的做法，很明显，暴力是无法处理这么大的数据的我们
来考虑对其进行优化，这里就要折半搜索了
折半搜索是针对暴力搜索的优化算法，本质上来说就是把搜索区间分为两
半，分开计算来优化时间复杂度，折半搜索的条件是分开搜索的结果可以
进行合并，针对此题，我们可以将查询区间一分为二, (1- mid) , (mid+1 -n)
分别进行暴力搜索，我们用 (a,b) 数组存储两次搜索的结果，即每个区间
符合条件的所有花费
最后我们将 (a) 数组从大到小排序，针对b里的每一个值 (bi)，我们在a数组里查询第一个大于(m- bi)的数的下标，答案加上下标减一的值，为什么要这么做？针对有序的(a)数组，对于每一个(bi)
我们所查找的下标减1的值就是(a)数组中与(bi)相加(<=m)的数的个数，
所以也有这么多方案是符合题意的。
为什么要查找第一个大于(m-bi)的数的下标？因为小于其下标的每一个值
加上(bi)的值一定小于等于(m)，但我们不知道a数组中是
否有(m-bi)，所以需要查找第一个大于它的数的下标减一，最后把答
案加起来即可，可能听起来有点迷糊，直接看代码要清晰许多。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=5e6;
inline int read(){
int f=1;
int ret=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-f;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
ret=ret*10+(ch^'0');
ch=getchar();
}
return ret*f;
}
int n,m;
int cnt1;
int cnt2;
int a[maxn];
int b[maxn];
int v[maxn];
void dfs1(int id,int mx,int sum){
if(sum>m){
return ;
}
if(id>mx){
a[++cnt1]=sum;
return ;
}
dfs1(id+1,mx,sum+v[id]);
dfs1(id+1,mx,sum);
}
void dfs2(int id,int sum){
if(sum>m){
return ;
}
if(id>n){
b[++cnt2]=sum;
return ;
}
dfs2(id+1,sum+v[id]);
dfs2(id+1,sum);
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
v[i]=read();
}
int mid=n>>1;
dfs1(1,mid,0);
dfs2(mid+1,0);
sort(a+1,a+1+cnt1);
int ans=0;
for(int i=1;i<=cnt2;i++){
ans+=upper_bound(a+1,a+1+cnt1,m-b[i])-a-1;
}
cout<<ans;
return 0;
}
原本搜索的时间复杂度为 (O(2^n))
优化为 (O(2^frac{n}{2}))
但最后需要加上合并的时间复杂度