祭司 (HG 2018.10.5 T2)

  考场中兴奋地看到了70%的数据范围，高高兴兴地打了个暴力 然后，正解真是妙啊~ 我们把第一个集合的suml叫做suml1，其他同理。那么答案显然是max(sumr1-suml2,sumr2-suml1),那么sumr1-suml2=(sumr1+suml1)-(suml2+suml1)=sum1-suml(1&2);那么还有一个也一样，sumr2-suml1=sumr(1&2)-sum1。 那么suml(1&2)和sumr(1&2)是常数，我们只用求出sum1的所有情况就行了。那么就是一个很简单很暴力的01背包， 开一个80000的f数组，f[i]判断i能不能取到。答案再暴力扫一遍取个min就好了 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define int long long using namespace std; int n,ans=0x7ffffff; int f[100010]; int a[210],s1=0,s2=0; signed main() { scanf("%lld",&n); for(int i=1;i<=n;i++) { int l,r; scanf("%lld%lld",&l,&r),s1+=l,s2+=r; a[i]=l+r; } f[0]=1; for(int i=1;i<=n;i++) for(int j=80000;j>=a[i];j--) if(f[j-a[i]]) f[j]=1; for(int i=0;i<=80000;i++) if(f[i]) ans=min(ans,max(i-s1,s2-i)); printf("%lld",ans); return 0; } ```