# FZU 2178 礼物分配 (折半搜索+二分)

```#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=1e9;
const double eqs=1e-9;
int v[40], w[40], c[17][1<<15], d[17];
int bin_search(int x, int f)
{
int low=0, mid, high=d[f]-1, ans=-1;
while(low<=high){
mid=low+high>>1;
if(c[f][mid]>=x) {
ans=mid;
high=mid-1;
}
else low=mid+1;
}
if(ans==-1){
return abs(c[f][d[f]-1]-x);
}
else if(ans==0){
return abs(c[f][0]-x);
}
else return min(abs(c[f][ans]-x),abs(c[f][ans-1]-x));
}
int main()
{
int t, n, i, min1, tot, m1, m2, ans1, ans2, al, ans, j, cnt;
//freopen("1.txt","r",stdin);
//freopen("2.txt","w",stdout);
scanf("%d",&t);
while(t--){
scanf("%d",&n);
m1=n>>1;
m2=n-m1;
min1=INF;
for(i=0;i<n;i++){
scanf("%d",&v[i]);
}
for(i=0;i<n;i++){
scanf("%d",&w[i]);
}
if(n==1){
printf("%d\n",min(v[0],w[0]));
continue ;
}
tot=1<<m1;
memset(d,0,sizeof(d));
memset(c,0,sizeof(c));
for(i=0;i<tot;i++){
ans1=ans2=cnt=0;
for(j=0;j<m1;j++){
if(i&(1<<j)) {
ans1+=v[j];
cnt++;
}
else ans2+=w[j];
}
c[cnt][d[cnt]++]=ans1-ans2;
}
for(i=0;i<=m1;i++){
sort(c[i],c[i]+d[i]);
}
al=1<<m2;
for(i=0;i<al;i++){
ans1=ans2=0;
cnt=0;
for(j=0;j<m2;j++){
if(i&(1<<j)) {
ans1+=v[j+m1];
cnt++;
}
else ans2+=w[j+m1];
}
ans=ans2-ans1;
//printf("%d\n",ans);
if((n&1)&&cnt){
min1=min(bin_search(ans,n/2+1-cnt),min1);
}
min1=min(bin_search(ans,n/2-cnt),min1);
}
printf("%d\n",min1);
}
return 0;
}
```

FZU 2178 礼物分配 (折半搜索+二分)

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊

Problem 2039 Pets Accept: 395 Submit: 1061 Time Limit: 1000 mSec Memory Limit : 32768 KB Prob

﻿﻿ J - Min Number Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Subm

Java 常用排序算法/程序员必须掌握的 8大排序算法 本文由网络资料整理转载而来，如有问题，欢迎指正
Problem Description Are you interested in pets? There is a very famous pets shop in the cente

K Best Time Limit: 8000MS Memory Limit: 65536K Total Submissions: 5288 Accepted: 1431 Case Ti