题目：https://www.luogu.org/problemnew/show/P4660
https://www.lydsy.com/JudgeOnline/problem.php?id=1168
自己一开始有这样的想法：枚举一边的手套一定选到 S 集合，设 c = 选到 S 里每个手套的最小需要选的手套个数，则 c = 这边所有手套个数 - (S里个数最小的手套个数-1) 。
设 ts = 另一边一定选到 S 集合里的至少一个手套的最小需要选的手套个数，则 ts = 不在 S 集合里的手套个数 + 1。
对于各种情况取min，再换一下枚举“一定"和”至少“的两边。
结果交到洛谷上只能得66分。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=(<<)+,INF=2e9+;
int n,a[N],b[N],s0,s1,c[M],bin[N],ans=INF,prn;
void init()
{
bin[]=;
for(int i=;i<=n;i++)bin[i]=bin[i-]<<;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]),s0+=a[i];
for(int i=;i<=n;i++)scanf("%d",&b[i]),s1+=b[i];
init();
for(int s=;s<bin[n];s++)
{
int d=INF,c=;
for(int j=;j<=n;j++)
if(s&bin[j-])
{
if(!a[j]){c=INF;break;}
d=min(d,a[j]);
}
if(c)continue;
c=s0-d+;
int ts=;
for(int j=;j<=n;j++)
if(!(s&bin[j-]))ts+=b[j];
if(c+ts<ans)ans=c+ts,prn=c;
else if(c+ts==ans)prn=min(prn,c);
}
for(int s=;s<bin[n];s++)
{
int d=INF,c=;
for(int j=;j<=n;j++)
if(s&bin[j-])
{
if(!b[j]){c=INF;break;}
d=min(d,b[j]);
}
if(c)continue;
c=s1-d+;
int ts=;
for(int j=;j<=n;j++)
if(!(s&bin[j-]))ts+=a[j];
if(c+ts<ans)ans=c+ts,prn=ts;
else if(c+ts==ans)prn=min(prn,ts);
}
printf("%d\n%d\n",prn,ans-prn);
return ;
}
囧
想来是那个枚举一定选到 S 集合的时候限制太僵硬，多选了一些。
然后得到了这个数据：
4
1 3 8 4
1 1 4 9
上面只要选13个，就一定会选到第一种或第二种；下面选2个一定会与上面重合。但在自己做法里不能体现。果然是那个地方限制得太僵硬。
试图想一些修补措施。然后越想越觉得题解的思路好好，最后还是弃疗了自己原来的做法。
题解是这样：设 ts 是对于集合 S 的，定义同上；则所有个数属于 [ S的颜色个数，在S里的手套个数 ] 的在另一边选择 x 个手套的答案 ans[ x ] 都要对 ts 取max，因为这些 x 可能取成 S 集合。
这里的左边界可以直接认为是0。因为如果 x 比那个小，则取了不足 S 的集合，对应的 ts 一定更大，即答案一定更大，所以对这个取个max也无妨。
然后似乎用单调队列来对那些 ans[ x ] 赋值？可以证明答案的 x 一定是 选一种颜色就全选了 +1 的那种个数，大约是从它对应的那个 ts 来看，则那个 +1 就是它和 ts 对上的那个颜色，其余颜色一定要选就全选，选的手套数更多。不过还是不太明白单调队列的原理。
直到看了这个题解：http://blog.sina.com.cn/s/blog_76f6777d0101bchd.html，才豁然开朗。
当然官方题解说得也是很明白的：b08.oi.edu.pl/downloads/booklet.pdf
大概是一种颜色全给左边选上或全给右边选上，一共 2^n 种左边(x)/右边(y)的值，每个值可看作以 ( 0,0 ) 和 ( x,y ) 为两个端点的矩形；左边/右边选手套的个数在这个矩形（含边界）里的，就可以选成这种不相交的集合，从而是不合法的；如果不被任意一个矩形包含，就一定是合法的；画出来的话发现备选答案就是一堆拐角（也许要判一下与坐标轴的夹角处），所以按一维排序、另一维单调栈维护好所有矩形交的轮廓，就可以在那些拐角里找答案了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=,M=(<<)+,INF=2e9+;
int n,a[N],b[N],bin[N],top,na,nb,pra=INF,prb=INF;
struct Node{
int a,b;
bool operator< (const Node &v)const
{return a==v.a?b<v.b:a<v.a;}
}t[M],sta[M];
void init()
{
bin[]=;for(int i=;i<=n;i++)bin[i]=bin[i-]<<;
}
void updt(int ta,int tb)
{
if((ll)ta+tb<(ll)pra+prb)pra=ta,prb=tb;
else if((ll)ta+tb==(ll)pra+prb&&ta<pra)pra=ta,prb=tb;
}
int main()
{
int tp;
scanf("%d",&tp);
for(int i=;i<=tp;i++)scanf("%d",&a[i]);
for(int i=;i<=tp;i++)scanf("%d",&b[i]);
for(int i=;i<=tp;i++)
{
if(!a[i])nb+=b[i]; else if(!b[i])na+=a[i];
else a[++n]=a[i],b[n]=b[i];
}
init();
for(int s=;s<bin[n];s++)
{
for(int i=;i<=n;i++)
if(s&bin[i-])t[s].a+=a[i];
else t[s].b+=b[i];
}
sort(t,t+bin[n]);
for(int i=;i<bin[n];i++)
{
while(top&&t[i].b>=sta[top].b)top--;
sta[++top]=t[i];
}
for(int i=;i<=top;i++)
updt(sta[i-].a+,sta[i].b+);
updt(sta[top].a+,);
updt(,sta[].b+);
printf("%d\n%d\n",pra+na,prb+nb);
return ;
}