FZUOJ Problem 2178 禮物分配
Problem 2178 礼物分配
題目鏈接： Click Here~
Problem Description
在雙胞胎兄弟Eric與R.W的生日會上，他們共收到了N個礼物，生日過後他們決定分配這N個礼物(numv+numw=N)。對於每個礼物他們倆有著各自心中的價值vi和wi，他們要求各自分到的礼物數目|numv-numw|<=1，並且各自所衡量的礼物價值的差值|sumv-sumw|盡可能小，現在他們想知道最小的差值是多少。
Input
第一行為一個整數表示數據組數T。 接下來T組數組，每組數據第一行為一個整數N。(N<=30) 第二行有N個整數，表示Eric所衡量的每個礼物的價值vi。(1<=vi<=10000000) 第三行也有N個整數，表示R.W所衡量的每個礼物的價值wi。(1<=wi<=10000000)
vcHLtv631svRy/eho77NysfV27DrsunV0qGjy7zP677NusPKx8/I1KS0psDts/bHsNK7sOuyv7fWtcS94bn7oaPIu7rzo6zU2tPDx7DD5rXEveG5+8XQts+688PmtcTH6b/2oaPV4tH5vs2/ydLU08W7r7W9wcsyXjE1tM63vcHLoaMKCjxicj4KCgo8cHJlIGNsYXNzPQ=="brush:java;">#include
#include
#include
#include
#include
using namespace std;
typedef __int64 LL;
const int INF = 1 << 30;
const int MAXN = 40;
vector num[MAXN];
int vi[MAXN],wi[MAXN];
int main() {
int n,T;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i = 0;i < n;++i) {
scanf("%d",&vi[i]);
}
for(int i = 0;i < n;++i) {
scanf("%d",&wi[i]);
}
for(int i = 0;i <= n;++i)
num[i].clear();
int n2 = n/2;
int cnt,sum1 ,sum2,sum;
for(int S = 0;S < 1 << n2; ++S) {
cnt = 0,sum1 = 0,sum2 = 0;
for(int i = 0;i < n2;++i) {
if(S >> i & 1) {
sum1 += vi[i];
cnt++;
} else {
sum2 += wi[i];
}
}
num[cnt].push_back(sum1 - sum2);
}
for(int i = 0;i < n2;++i) {
sort(num[i].begin(),num[i].end());
num[i].erase(unique(num[i].begin(),num[i].end()),num[i].end());
}
int ans = INF;
for(int S = 0;S < 1 << (n-n2);++S) {
sum,cnt = 0,sum1 = 0,sum2 = 0;
for(int i = 0;i < (n-n2);++i) {
if(S >> i & 1) {
sum1 += vi[i+n2];
cnt++;
} else {
sum2 += wi[i+n2];
}
}
int t = n - n2 - cnt;
sum = sum1 - sum2;
vector::iterator iter;
iter = lower_bound(num[t].begin(),num[t].end(),-sum);
if(iter != num[t].end() && abs(*iter + sum) < ans)
ans = abs(*iter + sum);
if(iter != num[t].begin()) {
--iter;
if(abs(*iter + sum) < ans) ans = abs(*iter + sum);
}
}
printf("%d\n",ans);
}
return 0;
}
/*
3
1 2 3
4 2 1
5
1 2 3 5 4
1 1 1 1 5
6
1 2 3 4 5 5
1 1 1 1 1 8
*/
