【题解】LuoGu5815：[CQOI2010]扑克牌

丰川样子小孩姐

于 2020-08-07 12:22:00 发布

阅读量175

点赞数 1

分类专栏：题解 LuoGu 二分文章标签：题解 LuoGu 二分贪心

本文链接：https://blog.csdn.net/ModestCoder_/article/details/107859755

版权

题解同时被 3 个专栏收录

435 篇文章

订阅专栏

LuoGu

255 篇文章

订阅专栏

二分

29 篇文章

订阅专栏

本文探讨了一种结合二分查找与贪心策略的算法应用案例，通过具体实例讲解了如何利用这两种算法解决特定问题，重点在于如何合理分配资源以达到最优解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

原题传送门
二分+贪心
目标是组出 $m i d$ 副牌，所以有两个要求

$J O K E R$ 不能不够
$J O K E R$ 最多用 $m i d$ 张

Code：

#include <bits/stdc++.h>
#define maxn 110
#define int long long
using namespace std;
int n, m, a[maxn];

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 check(int mid){
	int tmp = m;
	for (int i = 1; i <= n; ++i) if ((tmp -= max(0LL, mid - a[i])) < 0) return 0;
	if (m - tmp > mid) return 0;
	return 1;
}

signed main(){
	n = read(), m = read();
	int l = 0, r = 0, ans;
	for (int i = 1; i <= n; ++i) r += a[i] = read();
	while (l <= r){
		int mid = (l + r) >> 1;
		if (check(mid)) ans = mid, l = mid + 1; else r = mid - 1;
	}
	printf("%d\n", ans);
	return 0;
}