打卡信奥刷题（2940）用C++实现信奥题 P5815 [CQOI2010] 扑克牌

P5815 [CQOI2010] 扑克牌

题目描述

你有 $n$ 种牌，第 $i$ 种牌的数目为 $c_i$。另外有一种特殊的牌：joker，它的数目是 $m$。你可以用每种牌各一张来组成一套牌，也可以用一张 joker 和除了某一种牌以外的其他牌各一张组成 $1$ 套牌。比如，当 $n=3$ 时，一共有 $4$ 种合法的套牌：$\{1,2,3\}$，$\{J,2,3\}$，$\{1,J,3\}$，$\{1,2,J\}$。

给出 $n$，$m$ 和 $c_i$，你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里（可以有牌不使用）。

输入格式

第一行包含两个整数 $n$，$m$，即牌的种数和 joker 的个数。

第二行包含 $n$ 个整数 $c_i$，即每种牌的张数。

输出格式

输出仅一个整数，即最多组成的套牌数目。

输入输出样例 #1

输入 #1

3 4
1 2 3

输出 #1

3

说明/提示

样例说明

输入数据表明：一共有 $1$ 个 $1$，$2$ 个 $2$，$3$ 个 $3$，$4$ 个 joker。最多可以组成三副套牌：$\{1,J,3\}$，$\{J,2,3\}$，$\{J,2,3\}$，joker 还剩一个，其余牌全部用完。

数据范围

对于 $50\%$ 的数据，$2\le n\le 5$，$0\le m\le 10^6$，$0\le c_i\le 200$。

对于 $100\%$ 的数据，$2\le n\le 50$，$0\le m,c_i\le 5\times 10^8$。

C++实现

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

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容