自动搬运

查看原文

来自洛谷，原作者为

	C锥 AFO

搬运于2025-08-24 22:14:36，当前版本为作者最后更新于2020-08-10 18:54:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

显然二分 + 贪心；

每次二分一个套牌数目，设它为 $std$ 。贪心的使用 $joker$ 。对于每种牌，如果它的数目 $c_{i}$ 大于等于 $std$ ，那么不用管它，这种牌的数目是足够的。如果小于 $std$ ，那我们就要使用 $joker$ 了（能放则放，贪心思想）。

我们用一个 $tmp$ 容器记录一下 $joker$ 使用的次数，然后考虑 $tmp$ 等于多少时，这个 $std$ 不符合条件，也就是求一下 $tmp$ 的限制条件。

1. $tmp <= m$；

2. $tmp<=std$。

第一个是因为最多只有 $m$ 张 $joker$ ，第二个是因为每套牌中只能出现一张 $joker$ 。

那为什么这么贪心的放牌是对的呢？因为我们有一个限制条件 $tmp <= std$ ，我们不管 $joker$ 到底出现在哪，只管用了几张，只要这套牌用了 $joker$ ，这套牌别的位置就用给出的牌填上去。那如果别的牌不够呢，填不上去咋办？

假设我们现在紫色的牌只有四张，黑牌代表 $joker$ ，如果要填满就得用两张 $joker$ ，我们发现第三套牌（第三行）出现了两张 $joker$ ，不符合题意了，但是这时候 $tmp > std$ ，我们就可以直接判断不合法了。

下面是代码：

#include <iostream>
#include <cstdio>
#include <cctype>
#define mid ((l + r + 1) >> 1)

using namespace std;

inline long long read() { //快读
	long long s = 0, f = 1; char ch;
	while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
	return s * f;
}

const int N = 55, inf = 7e8 + 5e7 + 1; //自己瞎试了试 
int n, m, l, r;
int c[N];

bool judge(int std) {
	int tmp = 0, rest = std;
	for(int i = 1;i <= n; i++) {
		if(c[i] >= std) continue;
		tmp += (std - c[i]); rest -= (std - c[i]); //两个判断条件
		if(tmp > m || rest < 0) return 0;
	}
	return 1;
}

int main() {
	
	n = read(); m = read();
	for(int i = 1;i <= n; i++) c[i] = read(); 
	l = 1, r = inf;
	while(l < r) { //二分套牌数目
		if(judge(mid)) l = mid;
		else r = mid - 1;
	}
	printf("%d", l);

	return 0;
}

个人感觉挺好理解的，如果有不对的地方还希望dalao纠正QWQ