洛谷 P2431 正妹吃月饼 题解【贪心】

作者: wjyyy 分类: 二进制,解题报告,贪心 发布时间: 2018-07-11 15:24

点击量:14

 

   转化为二进制下的贪心。

 

题目描述

今天是中秋节。uim带来了一堆大小不同且味道各异的月饼。

 

这些月饼的质量分别是1g,2g,4g,8g,16g….后面一个是前面的2倍。每种只有一个。

 

uim让正妹随便吃。

 

正妹希望尝试尽可能多的口味,所以会吃尽可能多数量的月饼(不是重量)。而且她的确有些饿了,至少总共要吃掉A g的月饼才能满足。

 

然而正妹怕长胖,所以吃月饼不能合计超过B g。

 

她希望知道自己最多能吃多少个月饼。

 

输入输出格式

输入格式:

两个数,a,b.

 

输出格式:

正妹能吃到最多的数量。

 

输入输出样例

输入样例#1:
16 25
输出样例#1:
4

说明

解释 正妹可以吃1 2 4 16这4个(吃法可能不唯一)

 

30%数据,A,B<=1000

 

60%数据,A,B<=100000

 

100%数据,A,B<=2^63-1

 

题解:

   因为二进制下,\(\sum\limits_{i=0}^{62} x_i\times 2^i,x_i\in \{0,1 \}\)(\(x_i\)表示选或不选)可以表示\(0~2^{63}-1\)范围内所有数,所以这个题就要求找出l到r区间二进制下1最多的数,也就是求出\(\max_{l\le i\le r}\{popcount(i)\}\)。当l与r的区间差很小时,我们可以直接暴力求解,防止贪心出错。(实际上所有数据都是满足区间差较小而暴力可以AC,register+O2是玄学,考场上请勿全程暴力

 

   当区间差较大时,就要找出区间中1最多的数,首先是l,假设l的二进制数为1010 0111 1001,为了使1的数目增多而又尽可能不超过r,我们从右向左依次把0变成1,如果当前数字小于r则合法,否则跳出循环。为什么这样贪心是对的呢?我们从低位向高位枚举,每次只改变了能改变且增加1个数的最小范围,如果当前的最小范围都不满足,那么就到达极限了。当高位出现1低位反而出现0时,反而没有那个高位为0,低位全为1优了。(例如:1001 1000>0111 1111)

 

   Tip:在计算2的n次方时,不能直接用1<<n,当结果范围超出int时会溢出,因为1默认为int。

 

Code:

#include<cstdio>
#include<cstring>
int main()
{
    long long l,r;
    scanf("%lld%lld",&l,&r);
    if(r-l<=(1e6))//特判区间范围小,防止贪心出错
    {
        int ans=0;
        for(long long i=l;i<=r;i++)
        {
            long long t=i;
            int cnt=0;
            while(t)
            {
                cnt++;
                t-=(t&(-t));
            }
            ans=ans>cnt?ans:cnt;
        }
        printf("%d\n",ans);
        return 0;
    }
    long long one=1;//不能用1<<32以上,因为默认1是int
    for(long long i=0;i<=62;i++)
        if((l|(one<<i))<=r)
            l|=(one<<i);
    int cnt=0;
    while(l)
    {
        cnt++;
        l-=(l&(-l));
    }
    printf("%d\n",cnt);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */