扑克牌题解二分答案

题意就是给你N+1个种类的牌 然后N+1个牌是万能牌 ，这N+1种牌每个牌都有Ci个，然后问你这N+1个牌能够组成牌数为N，而且每个N张牌里面没有重复的牌，问你一共可以组成多少种。
题解：这题慕然一看感觉就是贪心，但是我们贪心做的话比如 1 2 3 （万能牌）10，答案很明显就是3，是不是可以贪心就是所有牌排序一次然后最少的2个数相加就是答案，但是如果样列是 100 100 （万能牌）100，这样答案岂不是是200，所以贪心有问题，那么换一个思想，我们来猜测答案，如果K种满足答案，那么K-1种也是满足答案，只不过种类数减少了，没有计算完全，那么是不是就是单调的了，我们很容易想到二分，直接去二分答案，mid=l+r,那么就是每种牌至少有mid个，万能牌去替换，我们最后要判断一下，是否替代过程中需要的万能牌数量小于我们有的，还有需要的的牌数小于答案的种类数。

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
#define fro for
#define it int
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
ll ans[maxx];
ll check(ll mid,ll n,ll m)
{
    ll dou=0;
    for(ll i=1;i<=n;i++)
    {
        if(mid>ans[i])
            dou+=mid-ans[i];
    }
    return dou<=m&&dou<=mid;
}
//ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
//inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
int main()
{
   ll n,m;
   cin>>n>>m;
  for(ll i=1;i<=n;i++)
    cin>>ans[i];
  ll l=1,r=1e9,ans;
  while(l<=r)
  {
      ll mid=l+r>>1;
      if(check(mid,n,m))
        ans=mid,l=mid+1;
      else
        r=mid-1;
  }
  cout<<ans<<endl;
    return 0;
}