题解 CF2096B

题意

给你 $n$ 种手套，第 $i$ 种手套有左手套 $l_i$ 只，右手套 $r_i$ 只。找到最小值 $x$ 使得选择任意 $x$ 只手套，总能保证有 $k$ 副不同的手套。

思路

数学题，贪心。

这道题需要使用抽屉原理（鸽巢原理，the pigeonhole principle）进行贪心。

把多于 $n$ 个的物体放到 $n$ 个抽屉里，则至少有一个抽屉里的东西不少于两件。

证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是 $n$，而不是题设的 $n + k \ (k \geq 1)$，故不可能。

如果每副手套左右各只有一只，答案为 $n + k$。此时的策略是先取每种手套的一只，然后取 $k$ 次另外一只。此时种类数为 $k$。

如果每副手套左右有若干只，考虑最差的情况，先取完每种手套的某一只手，再选取 $k$ 种手套取另外一只手。使用贪心法，先取每种手套较多的一只手，再降序排列取 $k - 1$ 种另一只手，最后再任意取 $1$ 只，此时种类数为 $k$。若 $(l_i, r_i)$ 按照 $\min(l_i, r_i)$ 降序排序，答案就是 $\sum_{i = 1}^n \max(l_i, r_i) + \sum_{i = 1}^{k - 1} \min(l_i, r_i) + 1$。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdint>
const int N = 2e5 + 10;
const int P = 1e9 + 7;
#define int int64_t
namespace IO {
	inline int read() {
		int x = 0, f = 1; char ch = getchar();
		while(ch > '9' || ch < '0') {
			if(ch == '-') f = -1; 
			ch = getchar();
		}
		while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch - 48), ch = getchar();
		return x * f;
	}
	void write(int x) {
		if(x < 0) {
			x = -x;
			putchar('-');
		}
		if(x > 9) write(x / 10);
		putchar(x % 10 + '0');
		return;
	}
}
namespace math {
	int qpow(int a, int x){
		int ans = 1;
		while(x) {
			if(x & 1) ans = ans % P * a % P;
			a = a * a % P;
			x >>= 1;
		}
		return ans;
	}
	int exgcd(int a, int b, int &x, int &y) {
		if(b == 0) {
			x = 1, y = 0;
			return a;
		}
		int d = exgcd(b, a % b, x, y);
		int xp = x;
		x = y;
		y = xp - a / b * y;
		return d;
	}
}
using namespace std;
using IO::read, IO::write;
using math::qpow;
int n, k;
int l[N], r[N];
void solve() {
	//clear
	//end clear
	n = read(); k = read();
	for(int i = 1; i <= n; i++) l[i] = read();
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		r[i] = read();
		if(l[i] > r[i]) swap(l[i], r[i]);
		ans += r[i];
	}
	sort(l + 1, l + n + 1, greater <int> ());
	for(int i = 1; i < k; i++) ans += l[i];
	ans++;
	cout << ans << "\n";
	return void(0);
}
int32_t main() {
	//int T = read();
	int T = read();
	while(T--) solve();
	return 0;
}//qwq

通过记录： https://codeforces.com/contest/2096/submission/319027880