当前位置：首页 > news >正文

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

news 2026/3/26 18:17:55

P5815 [CQOI2010] 扑克牌

题目描述

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

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

输入格式

第一行包含两个整数nnn，mmm，即牌的种数和 joker 的个数。

第二行包含nnn个整数cic_ici，即每种牌的张数。

输出格式

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

输入输出样例 #1

输入 #1

3 4 1 2 3

输出 #1

说明/提示

样例说明

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

数据范围

对于50%50\%50%的数据，2≤n≤52 \le n \le 52≤n≤5，0≤m≤1060 \le m \le 10^60≤m≤106，0≤ci≤2000 \le c_i \le 2000≤ci≤200。

对于100%100\%100%的数据，2≤n≤502 \le n \le 502≤n≤50，0≤m,ci≤5×1080 \le m,c_i \le 5 \times 10^80≤m,ci≤5×108。

C++实现

#include<iostream>#include<cstdio>#include<cctype>#definemid((l+r+1)>>1)usingnamespacestd;inlinelonglongread(){//快读longlongs=0,f=1;charch;while(!isdigit(ch=getchar()))(ch=='-')&&(f=-f);for(s=ch^48;isdigit(ch=getchar());s=(s<<1)+(s<<3)+(ch^48));returns*f;}constintN=55,inf=7e8+5e7+1;//自己瞎试了试intn,m,l,r;intc[N];booljudge(intstd){inttmp=0,rest=std;for(inti=1;i<=n;i++){if(c[i]>=std)continue;tmp+=(std-c[i]);rest-=(std-c[i]);//两个判断条件if(tmp>m||rest<0)return0;}return1;}intmain(){n=read();m=read();for(inti=1;i<=n;i++)c[i]=read();l=1,r=inf;while(l<r){//二分套牌数目if(judge(mid))l=mid;elser=mid-1;}printf("%d",l);return0;}