BZOJ 1816 扑克牌(二分)

由于答案具有单调性，考虑二分答案并验证。

如果能凑齐x堆，因为每个joke在一个牌堆里最多只能用一次，则至多只能用min(x,m)个joke.

对于每个牌，如果这个牌的总数小于x，用joke补齐剩下的，如果能补齐那么一定能组成x堆。

简单证明: 补齐完后的牌堆里每用joke一个，一定能在其他牌里面凑齐n-1个不是joke的牌。

考虑反证法，如果取某一个joke后，剩下的牌组有一个只剩下joke的话。这是不可能的，因为joke总数至多为x。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int a[N], n, m;

bool check(int x){

    LL res=;

    FOR(i,,n) {

        if (a[i]>=x) continue;

        res+=(x-a[i]);

    }

    return res<=min(m,x);

}

int main ()

{

    int ma=;

    scanf("%d%d",&n,&m);

    FOR(i,,n) scanf("%d",a+i), ma=max(ma,a[i]);

    int l=, r=ma+m+, mid;

    while (l<r) {

        mid=(l+r)>>;

        if (l==mid) break;

        if (check(mid)) l=mid;

        else r=mid;

    }

    printf("%d\n",l);

    return ;

}

巴特西

BZOJ 1816 扑克牌(二分)

最新文章

热门文章