【练习】[CQOI2010]扑克牌

[CQOI2010]扑克牌

https://ac.nowcoder.com/acm/problem/19916

题目

题目描述：

你有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，你的任务是组成尽量多的套牌。

每张牌最多只能用在一副套牌里（可以有牌不使用）。

输入描述：

第一行包含两个整数n, m，即牌的种数和joker的个数。
第二行包含n个整数ci，即每种牌的张数。

输出描述：

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

解析

1）知识点

这道题就是一道简单的二分，不过有一点小小的特判挂了我一会儿。

2）看题目

这道题目的意思就是joker代替任何牌，每组牌最多用一次joker，求最大构成的牌组数。

3）算法分析

一看到这道题我首先想到的就是简单排序，然后东搞西搞。但是搞不出来。
只要想到二分，这道题就非常的简单了。
二分，我们当然是二分答案，二分我们到底可以形成多少组。
二分以后怎么判断呢？假如现在我们猜测可以形成x组，是不是表示，我们可以用joker，将比这个组数位置小的全都用joker填补。
栗子：我们现在有12345，这五个数，我们猜测可以形成三组。那么说明1和2可以被joker填满。
（这里要注意一个点：题目讲了同一行里面不能出现两张相同的牌，说明joker不能在同一组里面用两次）
然后我们求出在这个猜测下需要用到的joker数量，和当前有的joker数量和猜测的组数里面的较小值进行比较（因为有几组，最大就只能用joker几次，每组一次嘛）。
如果我们算出来用的joker数量小于可用的（当前有的joker数量和猜测的组数里面的较小值），表示joker有多，就删掉左域表示多选点。反之亦然。
那么按照上面说的，套二分模板就好了。

4）算法操作

所以我们还是先套二分模板：

while (l <= r) {
    int mid = l + r >> 1;
    if (judge(mid)) l = mid + 1;
    else r = mid - 1;
}

然后我们就要开始写判断函数了：
我们一趟遍历过去，把小于二分猜测x值的所有数，全部求差值（x - poker[i]），再求和：
```
for (int i = 1; i <= n; i++)
        if (poker[i] < x)
        sm += x - poker[i];
```
最后做个判断就好了：
```
return sm <= min(joker, x);
```

5）打代码

首先是输入数据。
然后套二分模板，按上面二分就好了。
下面全代码~

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int INF = 0x3f3f3f3f;
int n, joker; 
int poker[54];
//全局变量区

bool judge(int x) {
    ll sm = 0;
    for (int i = 1; i <= n; i++)
        if (poker[i] < x)
             sm += x - poker[i];
    return sm <= min(joker, x);
}
//函数预定义区

int main() {
    IOS;
    cin >> n >> joker;
    for (int i = 1; i <= n; i++) cin >> poker[i];
    int l = 0, r = INF;
    while (l <= r) {
        int mid = l + r >> 1;
        if (judge(mid)) l = mid + 1;
        else r = mid - 1;
    }
    cout << r << endl;
    return 0;
}
//函数区

牛客算法竞赛入门课题解文章被收录于专栏

憨憨的专栏