[Baltic2008]Gloves

Time Limit:10000MS Memory Limit:165536K
Total Submit:43 Accepted:16
Case Time Limit:1000MS

Description

手套被放在了两个抽屉里, 所有的左手套放在左边的抽屉里, 所有的右手套放在右边的抽屉里．
手套一共有N种颜色, 已知两个抽屉每种颜色的手套各有多少只, 如果随便在左边拿一只, 右边拿一只
很可能会造成拿到一只红色的左手套和一只蓝色右手套… 现想知道应该从左边的抽屉取出多少只左手套(设为x)
右边的抽屉取出多少只右手套(设为y), 满足至少可以找到一对匹配的手套(即颜色相同), 并且x + y最小
如果有多个(x, y)满足x + y最小, 你希望满足x尽可能的小
不妨设 每个抽屉里每只手套被取出的概率是等价的．
输入文件
输入文件第一行中有一个正整数N,表示颜色的种数．
第二行有N个非负整数, 表示左抽屉中每种颜色的左手套的个数．
第三行有N个非负整数, 表示右抽屉中每种颜色的右手套的个数．
输出文件
你需要输出满足题目条件的(x, y)．

Input

输入文件第一行中有一个正整数N,表示颜色的种数．
第二行有N个非负整数, 表示左抽屉中每种颜色的左手套的个数．
第三行有N个非负整数, 表示右抽屉中每种颜色的右手套的个数．

Output

输出满足题目条件的(x, y)．

Sample Input

Sample Output

Source
饿。。我的算法超级慢，运行了接近6000MS囧。。。
这道题还是有点意思的，一开始我没什么想法，然后注意将这个N个颜色划分成2部分，一种左手套设和为L，一种右手套，设和为R，那么对于任何x<=L&&y<=R的都将不行。。于是枚举所有的划分（1<<n）。。算出每种约束，把所有约束看成点，然后去掉被包含的点，然后按X排序，那么答案只可能出现在两个相邻的点组成的矩形的左下角的右上一格。。很好证明就不多说了。。
Code：

#include<iostream>#include<algorithm>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=20;typedef long long ll;const ll inf=1LL<<60;int A[maxn],B[maxn],n,m=0;ll L=0,R=0;struct Point{ ll x,y; Point(){} Point(ll _x,ll _y):x(_x),y(_y){} bool operator<(const Point&o)const { if(x!=o.x)return x<o.x; return y<o.y; }}P[1<<maxn];void Dfs(int p,ll l,ll r){ if(p==n){P[m++]=Point(l,r);return;} Dfs(p+1,l+A[p],r);Dfs(p+1,l,r+B[p]);}int main(){ //freopen("in","r",stdin); cin>>n;rep(i,n)cin>>A[i],L+=A[i];rep(i,n)cin>>B[i],R+=B[i]; Dfs(0,0,0);sort(P,P+m);int p=0;ll l=inf,r=inf; for(int i=0;i<m;i++) { while(p&&P[p-1].y<=P[i].y)p–; P[p++]=P[i]; } m=p; for(int i=0;i<m-1;i++) { ll a=P[i].x+1,b=P[i+1].y+1; if(!(a<=L&&b<=R))continue; if(a+b>l+r)continue; if(a+b<l+r)l=a,r=b; else if(a<l)l=a,r=b; } cout<<l<<" "<<r<<endl;}2 8100%的测试数据, N <= 20, 0 <= ai, bi <= 108．40 7 1 61 5 0 6