题意:给你n对人, 每一对都有2个人,每个人分别有一个值, 现在将每队人拆开塞入2组,要求分完这n对人之后,2个组的差值最小。
题解:将每队人的差值算出来,并且对于差值求和 tot, 然后这个题目就变成了给你n个数, 分成2组, 求差值最小的题目, 对差值进行跑背包操作就好了。
这份代码用bitset完成的, 因为在练习这个东西。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9+;
const int N = *+;
bitset<N> b;
int a[N];
int main(){
///Fopen;
int T;
scanf("%d", &T);
while(T--){
b.reset();
b[] = ;
int n, v, u, tot = ;
scanf("%d", &n);
for(int i = ; i <= n; i++){
scanf("%d%d", &u, &v);
a[i] = abs(u-v);
tot += a[i];
}
for(int i = ; i <= n; i++){
b |= (b << a[i]);
}
int l = ;
for(int i = tot/; i >= ; i--){
if(b[i]){
l = i;
break;
}
}
int ans = tot - *l;
printf("%d\n", ans);
}
return ;
}