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

点击量：148

   转化为二进制下的贪心。

目录

题目描述

今天是中秋节。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;
}