洛谷题面

题目大意

你有 \(n\) 种牌，第i种牌的数目为 \(c_i\)。另外有一种特殊的牌：\(\rm joker\)，它的数目是 \(m\)。你可以用每种牌各一张来组成一套牌，也可以用一张 \(\rm joker\) 和除了某一种牌以外的其他牌各一张组成 \(1\) 套牌。

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

题目分析

发现 \(\rm Joker\) 牌的作用只是合法的代替其它类型的卡牌而已，所以我们称 \(\rm Joker\) 为 \(0\) 号卡牌。

稍微想想：能够拼出 \(k\) 组卡牌，一定也能拼出 \(k-1,k-2,\cdots,2,1\) 组卡牌。故答案具有单调性。

于是考虑二分答案，二分能够拼出的套牌数量。

\(\rm Judge\) 函数：

inline bool Judge(int now)
{
	int tp=0;
	
	for(register int i=0;i<=n;i++)
	{
		if(now>a[i])//如果牌数大于 now，即可以出牌来拼
		{
			tp+=now-a[i];
		}
	}
	
	return tp<=now;//表示可以拼出 now 组
} 

随后照常二分即可。

代码

//2021/11/7

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <climits>//need "INT_MAX","INT_MIN"

#define int long long 

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<<c<<que

#define cek(c) puts(c)

#define blow(arr,st,ed,w) for(register int i=(st);i<=(ed);i++)cout<<arr[i]<<w;

#define speed_up() std::ios::sync_with_stdio(false)

namespace Newstd
{
	inline int read()
	{
		char c;
		bool flag=false;
		while((c=getchar())<'0' || c>'9')
		{
		    if(c=='-') flag=true;
		}
		int res=c-'0';
		while((c=getchar())>='0' && c<='9')
		{
		    res=(res<<3)+(res<<1)+c-'0';
		}
		return flag?-res:res;
	}
	inline void print(int x)
	{
		if(x<0)
		{
			putchar('-');x=-x;
		}
		if(x>9)
		{
			print(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const int ma=55;

int a[ma];

int n,m;

inline int Abs(int x)
{
	return x>0?x:-x;
}

inline bool Judge(int now)
{
	int tp=0;
	
	for(register int i=0;i<=n;i++)
	{
		if(now>a[i])
		{
			tp+=now-a[i];
		}
	}
	
	return tp<=now;
} 

#undef int

int main(void)
{
	#define int long long
	
	n=read(),m=read();
	
	a[0]=m;
	
	for(register int i=1;i<=n;i++)
	{
		a[i]=read();
	}
	
	int l=0,r=6e8,ans;
	
	while(l<r)
	{
		int mid=(l+r+1)>>1;
		
		if(Judge(mid)==true)
		{
			l=mid;
			
			ans=l;
		}
		
		else
		{
			r=mid-1;
		}
	}
	
	printf("%lld\n",ans);
	
	return 0;
}