首页 > 代码库 > FZU 11月月赛D题：双向搜索+二分
FZU 11月月赛D题：双向搜索+二分
/*
双向搜索感觉是个不错的技巧啊
*/
题目大意：
有n的物品(n<=30)，平均（两个人得到的物品差不能大于1）分给两个人，每个物品在每个人心目中的价值分别为(vi，wi)
问两人心目中的价值差最小是多少。
分析：
直接暴搜目测会超时
想到先搜索前一半，用数组a[0][i]保存第一个人在前半段取 i 个物品两个人的差的所有情况；
再搜索后一半保存两个人的差的相反数，用相同的规则保存在a[1][]中。
要想总差最小只需要
a[0][i]-a[1][num-i] （num=n/2或 n/2+1）的绝对值最小即可..
找这个最小值可以用二分查找优化
然后就不会超时了
ac代码：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define inf 500000000int a[2][32][70000];int nn[2][32];int v[32],w[32];int n;void dfs(int now,int e,int num,int ans,int flag){ if(now>e) { a[flag][num][nn[flag][num]++]=ans; return; } int p=flag?(-1):1; dfs(now+1,e,num,ans-p*w[now],flag); dfs(now+1,e,num+1,ans+p*v[now],flag);}void ini(){ scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",v+i); } for(int i=0;i<n;i++) { scanf("%d",w+i); }}int fun(int val,int pos){ int res=inf; int num=nn[1][pos]; if(val>a[1][pos][num-1]) { return abs(val-a[1][pos][num-1]); } int k=upper_bound(a[1][pos],a[1][pos]+num,val)-a[1][pos]; res=min(res,abs(val-a[1][pos][k])); if(k) { res=min(res,abs(val-a[1][pos][k-1])); } return res;}void solve(){ int ans=inf; memset(nn,0,sizeof(nn)); dfs(0,n/2-1,0,0,0); dfs(n/2,n-1,0,0,1); for(int i=0;i<2;i++) { for(int j=0;j<16;j++) { sort(a[i][j],a[i][j]+nn[i][j]); } } for(int i=0;i<=n/2;i++) { for(int j=0;j<nn[0][i];j++) { int x=a[0][i][j]; int k=n/2-i; ans=min(ans,fun(x,k)); if(n%2) { k=n/2+1-i; ans=min(ans,fun(x,k)); } } } printf("%d\n",ans);}int main(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif int t; scanf("%d",&t); while(t--) { ini(); solve(); } return 0;}
FZU 11月月赛D题：双向搜索+二分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。