BZOJ1816 [Cqoi2010]扑克牌

2014.12.24 12:19 Wed| 0 visits oi_2015| 2015_刷题日常| Text

Solution

貌似是一道水题?

如果能组成n套牌,则至多使用Joker $\min(m,n)$ 次。这样便可以二分判定答案。

Code

#include <bits/stdc++.h>
using namespace std;

int n,m,a[51];

bool check(int now)
{
    int t=min(m,now);
    for(int i=1;t>=0&&i<=n;i++)
        t-=(now-a[i])*(a[i]<now);
    return t>=0;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    int l=1,r=600000000,ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans<<endl;
}