刷题记录:牛客NC19916[CQOI2010]扑克牌

传送门:牛客

题目描述:

你有n种牌，第i种牌的数目为ci。另外有一种特殊的牌：joker，它的数目是m。你可以用每种牌各一张来
组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如，当n=3时，一共
有4种合法的套牌：{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和ci，你的任务是组成尽量多的套牌。每张
牌最多只能用在一副套牌里（可以有牌不使用）。
输入:
3 4
1 2 3
输出:
3
1
2
3
4
5
6
7
8
9

一道当年重庆的省选题,洛谷上评级为蓝,牛客网上的四星题,但是并没有我们想象的那么难,仔细看看竟然还是可做的

首先这种题目是一种典型的二分答案的题目,有了二分答案的想法接下来我们只要去思考check部分该怎么写即可.仔细看一下题目,我们发现其实joker并没有什么其他的不一样的功能,只是单纯的在原来n张牌的基础上增加了一张牌而已,此时我们的题目就转化成了从n+1堆中每堆选取1张牌,对于这个问题我们有以下的想法,首先肯定考虑能不能贪心的算法,但是对于这道题,似乎是有一点的困难,难点在于如何比较是否使用joker这张牌,我们似乎很难判断是否使用joker更优,然后我们在看一下我们的题目,会发现有一个转化的方式,我们可以将原问题转化为这样的一个方式:即在N+1的堆中分别取一个,再重新拿回去一个,判断需要拿回去的牌的数量和我们的mid想比,为什么这么做呢,是因为假设我们的mid值是合法的话,而这些牌依旧不够用,就说明因为我们在N+1的堆中多拿的肯定是这些缺牌的堆的部分,假设缺失的牌数>=mid的话,说明即使将多拿的mid的数量的牌都填补过去还是不够,说明肯定是不合法的

注意点:注意使用longlong,注意r的初始值,要开足

具体代码:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
ll n,m;
ll c[maxn];
ll max(ll aa,ll bb){
	if(aa>bb) return aa;
	else return bb;
}
ll check(ll mid) {
	ll sum=0;
	for(int i=1;i<=n+1;i++) sum+=max(mid-c[i],0);
	if(sum<=mid) return true;
	else return false;
}
int main() {
	n=read();m=read();
	for(int i=1;i<=n;i++) {
		c[i]=read();
	}
	c[n+1]=m;
	ll l=0,r=750000000;ll ans;
	while(l<=r) {
		ll mid=(l+r)>>1;
		if(check(mid)) {
			l=mid+1;
			ans=mid;
		}else {
			r=mid-1;
		}
	}
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54