自动搬运

查看原文

来自洛谷，原作者为

	ModestCoder_ 这个家伙不懒，但还是什么也没有留下

搬运于2025-08-24 22:02:23，当前版本为作者最后更新于2019-08-29 19:31:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

从样例下手

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;
}