[CQOI2010] 扑克牌

原题链接

这道题是一道隐蔽的二分答案题（01规划）。但由题目中的“最多”一词也可以知晓。

我们可以把题目中的joker类比成万能牌，但一套牌中只能最多有一张万能牌。

那么对于预期答案k，我们想要验证，只需要sum+=min(0,k-a[i]);然后我们要判断sum<=m并且sum<=k(一套牌中只能最多有一张万能牌)

主要代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=55;
int a[N],n,m;
bool check(int mid){
    int cnt=1;
    ll sum=0;
    while (a[cnt]<mid && cnt<=n) sum=sum+ll(mid-a[cnt++]);
    return (sum<=ll(m) && sum<=ll(mid));
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    int left=0,right=1e9;  //5e8数量级是过不了的
    while (left+1<right){
        int mid=left+(right-left>>1);
        if (check(mid)) left=mid;
        else right=mid;
    }
    printf("%d\n",left);
    return 0;
}