C++

「二分答案 & 贪心」BZOJ-1816 扑克牌

CQOI-2010 扑克牌

Description

你有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,你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里(可以有牌不使用)。

Input

第一行包含两个整数n, m,即牌的种数和joker的个数。第二行包含n个整数ci,即每种牌的张数。

Output

输出仅一个整数,即最多组成的套牌数目。

Sample Input

3 4
1 2 3

Sample Output

3

样例解释

输入数据表明:一共有1个1,2个2,3个3,4个joker。最多可以组成三副套牌:{1,J,3}, {J,2,3}, {J,2,3},joker还剩一个,其余牌全部用完。
数据范围
50%的数据满足:2 < = n < = 5, 0 < = m < = 10^ 6, 0< = ci < = 200
100%的数据满足:2 < = n < = 50, 0 < = m, ci < = 500,000,000。

题解报告

哇,看到100%数据吓一跳,果断二分,判断函数需要贪心,如果暴搜的话TLE就会向你招手哦,仔细想想好像和某年NOIp2013 d1t1有几分相似,这道题多了个二分贪心,就变成省选题了么…

二分mid作为最多能组成的牌的数目,接下来就是判断。我们可以看成将牌全部摆在桌子上,然后拿Joker补全空隙,但是需要注意的是,这个是贪心思想,需要证明正确性,因为要求每套牌只能拿一个Joker代替,x是这些扑克牌最大套数,m是Joker数量,m可以局限最大套数,因为每一套必须小于等于m,所以用 min(m,x) 来限制套数,如果用m将扑克牌搭出了x套的条件满足,则必然可以证明贪心的正确性。

具体内容见代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int n,m,a[60],l,r,mid,ans;
bool ok(int x){
    int k=min(m,x);//k为需要的Joker数量,并且每套最多1个Joker。
    for(int i=1;i<=n;i++){
        if(a[i]<x) k-=(x-a[i]);//Joker数量减去对于第i个牌要想搭成x套牌需要的Joker数
        if(k<0) return 0;
    }
    return 1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int l=1;r=600000000;
    while(l<=r){
        mid=(l+r)>>1;
        if(ok(mid)) ans=mid,l=mid+1;//第一次写的l=mid 结果二分跑炸了
        else r=mid-1;
    }
    cout<<ans<<endl;
    return 0;
}
分享到