正妹吃月饼
题目描述
今天是中秋节。uim 带来了一堆大小不同且味道各异的月饼。
这些月饼的质量分别是 1g,2g,4g,8g,16g....后面一个是前面的2倍。每种只有一个。
uim让正妹随便吃。
正妹希望尝试尽可能多的口味,所以会吃尽可能多数量的月饼(不是重量)。而且她的确有些饿了,至少总共要吃掉 \(A\) g的月饼才能满足。
然而正妹怕长胖,所以吃月饼不能合计超过 \(B\) g。
她希望知道自己最多能吃多少个月饼
输入格式
两个数,\(A,B\)。
输出格式
正妹能吃到最多的数量
样例 #1
样例输入 #1
16 25
样例输出 #1
4
提示
解释 正妹可以吃1 2 4 16这4个(吃法可能不唯一)
30%数据,\(1\le A,B \le 1000\)
60%数据,\(1 \le A,B \le 100000\)
100%数据,\(1 \le A,B \le 2^{63}-1\)
思路:最少吃 \(Ag\) 月饼,那么从 \(A\) 往上找找到超过 \(B\) 的位置就可以了。
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long A, B, tmp;
cin >> A >> B;
for (int i = 0; i <= 60; i++) {
tmp = 1ll << i;
if ((A | tmp) <= B) {
A |= tmp;
}
}
int cnt = 0;
while (A) {
if (A & 1) cnt++;
A >>= 1;
}
cout << cnt << endl;
return 0;
}
标签:le,进制,月饼,样例,long,正妹,P2431
From: https://www.cnblogs.com/CYLSY/p/16978776.html