题目

题目描述：
你有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）算法分析

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

4）算法操作

  1. 所以我们还是先套二分模板： 
    while (l <= r) {
    int mid = l + r >> 1;
    if (judge(mid)) l = mid + 1;
    else r = mid - 1;
}
  2. 然后我们就要开始写判断函数了：
  3. 我们一趟遍历过去，把小于二分猜测x值的所有数，全部求差值（x - poker[i]），再求和： 
    for (int i = 1; i <= n; i++)
        if (poker[i] < x)
        sm += x - poker[i];
  4. 最后做个判断就好了： 
    return sm <= min(joker, x);

5）打代码

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

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;
}
//函数区