首页 > 代码库 > 曹文夏令营 2016 普及组 第贰轮 游戏

曹文夏令营 2016 普及组 第贰轮 游戏

游戏

以下是原题

【问题描述】
/*“Ran,今天我要在Hakase 家打游戏,不回来了。”
“Ran,Hakase 新发明了游戏,我今天住博士家。”
“Ran,Conan 今天要在我家通宵打游戏。”
终于有一天,电脑被打坏了……2333
所以Conan 要前往专卖店买新的,正好专卖店正在促销,*/

一共有三种礼包:
豪华礼包:一个U 盘、一个鼠标和一个机械键盘。
幸运礼包:一个U 盘、两个鼠标。
普通礼包:两个U 盘、一个鼠标。
卖店内准备了a 个U 盘、b 个鼠标和c 个机械键盘。为了给顾客带来足
够多的惊喜,店长希望相邻两位领礼包的顾客拿到的礼包类型都是不同的。店长
想知道这些奖品最多可以发出多少份礼包。可是店长毕竟没有Conan 聪明,所以
请教Conan,可是Conan 要急着回去打游戏,所以就交给你啦。
【输入格式】
从文件store.in 中读入数据。
输入第一行包含一个正整数T。
接下来T 行每行包含3 个正整数a, b, c,依次表示U 盘、鼠标和机械键盘各
有多少个。
【输出格式】
输出到文件store.out 中。
输出T 行,每行一个整数,表示最多能发出多少份礼包。
【样例输入】
24
4 0
1 1 1
【样例输出】
2
1
【数据规模与约定】
对于 30%的数据满足T<=10,a,b,c<=30。
对于 60%的数据满足T<=100,a,b,c<=300,000。
对于 100%的数据满足T<=100000,0<=a,b,c<=1,000,000。

====================分==============割================线========================

所以实际上这道题实际上就是有a个U盘,b个鼠标,c个键盘,将它们分成不连续的三种礼包,求最多能分出多少礼包。

首先根据数据范围算复杂度,⑩万的数据最大也就只能用O(n*logn)左右的算法了。答案仅为最多礼包数,T组数据,

所以二分枚举答案是首选。接下来就是如何检验枚举出来的数是否成立了,对于我们枚举出的x,

在满足相邻礼包不相同的条件下,三种礼包中 (送出礼包数较小两种的礼包数量之和)>=x/2。再来看这三种礼包:

  U盘 鼠标 机械键盘
豪华礼包 1 1 1
幸运礼包 1 2  
普通礼包 2 1  

 

不难发现,每一种礼包都是一个U盘、一个鼠标,再加上 { U盘、鼠标、机械键盘 } 中三选一构成,

就是说每个礼包的保底是1个U盘和1个鼠标,外加上三选一,

所以验证方法实际上就出来了:

a个U盘,b个鼠标,c个键盘,枚举的x个礼包,首先需要a>=x,b>=x,

然后a,b都减去x,剩余a,b,c的值就是对应的普通、幸运、豪华礼包个数,

a,b,c中两两相加之和最小的如果>=x/2,则此方案成立。

 

#include<cstdio>
int T,a,b,c,l,r,mid,ans;
bool ch(int x)
{
    int a1=a,b1=b,c1=c;
    a1-=x;b1-=x;
    if(a1<0||b1<0)return 0;
    int mi=a1+b1;
    if(a1+c1<mi)mi=a1+c1;
    if(b1+c1<mi)mi=b1+c1;
    if(mi<x/2)return 0;
    return 1;
}
int main()
{
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&a,&b,&c);
        l=0;r=(a+b+c)/3;mid=(l+r)/2;
        while(l+5<r)//二分时左右间距开到5会容错率高一点(笑 
        {
            if(!ch(mid))r=mid-1;
            else l=mid;
            mid=(l+r)/2;
        }ans=l;
        for(int i=l;i<=r;i++)
        {
            if(!ch(i))break;
            ans=i;
        }
        printf("%d\n",ans);
    }
}

 

//高中生来水普及组的题真?丢人

 

曹文夏令营 2016 普及组 第贰轮 游戏