首页 > 代码库 > [BZOJ 1816] [Cqoi2010] 扑克牌 【二分答案】
[BZOJ 1816] [Cqoi2010] 扑克牌 【二分答案】
题目链接：BZOJ - 1816
题目分析
答案具有可以二分的性质，所以可以二分答案。
验证一个答案 x 是否可行，就累加一下各种牌相对于 x 还缺少的量，如果总和超过了 x 或 m ，就不可行。
因为，当使用的joker小于等于 x 时，才可以通过合适地安排顺序使得每组牌中至多有一张 joker 。
代码
#include <iostream>#include <cstdlib>#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>using namespace std;const int MaxN = 50 + 5;int n, m, MaxA, Ans;int A[MaxN];bool Check(int x) { int t = min(x, m); for (int i = 1; i <= n; ++i) { if (A[i] < x) { t -= x - A[i]; if (t < 0) return false; } } return true;}int main() { scanf("%d%d", &n, &m); MaxA = -1; for (int i = 1; i <= n; ++i) { scanf("%d", &A[i]); MaxA = max(MaxA, A[i]); } Ans = 0; int l, r, mid; l = 0; r = MaxA + m; while (l <= r) { mid = (l + r) >> 1; if (Check(mid)) { Ans = mid; l = mid + 1; } else r = mid - 1; } printf("%d\n", Ans); return 0;}
[BZOJ 1816] [Cqoi2010] 扑克牌 【二分答案】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。