题解 P4660 【[BalticOI 2008]手套】

· · 题解

先随便选择左手套的颜色，把一些颜色的左手套都取光，那么在这个情况下，右手套至少取多少只？

从样例下手

4
0 7 1 6
1 5 0 6
左手套选了2、3两种颜色，拿了8只手套，右手套就至少拿8个（1、4两种颜色手套都要拿，再多拿一只）

对于每种取颜色方案，都会得到一个二元组(x,y)表示这些颜色的左手套数量之和x，这些颜色的补集的右手套数量之和y

把这个二元组对应到平面直角坐标系里面，得到几何意义：(0,0)到(x,y)组成的矩形中的点都是不合法的方案

然后可以O(2^n)枚举所有颜色方案得到2^n个矩形，把这写矩形弄到坐标系里面，形成如下图

其中红点表示一个二元组，因为任何矩形里面的点是不可行的，然后发现这些矩形有一个外围

蓝线表示外围，发现图中黄点是可以代表所有方案的，现在把问题转化成，对于所有黄点(x,y)，求min(x+1+y+1)

因为光是x和y是不满足要求，都各多取一只才满足要求

然后求黄点的坐标就是先预处理出所有矩形的右上角，然后排个序(x为第一关键字，y为第二关键字)，用个单调栈把黄点处理出来再算答案

Code：

#include <bits/stdc++.h>
#define maxn 2000010
using namespace std;
struct node{
    int x, y;
}s[maxn], stk[maxn];
int a[maxn], b[maxn], n, tot, top, ans1, ans2;

inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}

bool cmp(node x, node y){ return x.x == y.x ? x.y > y.y : x.x < y.x; }

int main(){
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n; ++i) b[i] = read();
    tot = 1 << n; 
    for (int i = 1; i <= tot; ++i)
        for (int j = 0; j < n; ++j)
            if ((i >> j) & 1) s[i].x += a[j + 1]; else s[i].y += b[j + 1];
    sort(s + 1, s + 1 + tot, cmp);
    s[0].x = s[1].x - 1;
    for (int i = 1; i <= tot; ++i){
        if (s[i].x == s[i - 1].x) continue;
        while (top && stk[top].y <= s[i].y) --top;
        stk[++top] = s[i];
    }
    int Max = 2147483647;
    for (int i = 2; i <= top; ++i)
        if (stk[i - 1].x + stk[i].y + 2 < Max)
            Max = stk[i - 1].x + stk[i].y + 2, ans1 = stk[i - 1].x + 1, ans2 = stk[i].y + 1;
    printf("%d\n%d\n", ans1, ans2);
    return 0;
}