http://www.lydsy.com/JudgeOnline/problem.php?id=1192
看到题我就好像想起以前小学升学考数学的最后一题,将一条金块分割最少的部分,使得每一天都能够支付给店主人任意的钱,这个方法很简单,就是将金块分割成1、 2、 4、 8、 。。。 2^k 使得 2^k<=n,最后将剩余的放入一个钱袋即可。
我是模拟的,logn的算法。1A了。看了题解才发现这题o1就可以出来。。。orz。直接算logn的上界就是答案。。。
#include <cstdio>
using namespace std; int ans, n; int main() {
scanf("%d", &n);
int m=1;
while(n>0) {
ans++;
n-=m;
m<<=1;
}
printf("%d\n", ans);
return 0;
}
Description
鬼谷子非常聪明,正因为这样,他非常繁忙,经常有各诸侯车的特派员 前来向他咨询时政。有一天,他在咸阳游历的时候,朋友告诉他在咸阳最大的拍卖行(聚宝商行)将要举行一场拍卖会,其中有一件宝物引起了他极大的兴趣,那就 是无字天书。但是,他的行程安 排得很满,他他已经买好了去邯郸的长途马车标,不巧的是出发时间是在拍卖会快要结束的时候。于是,他决定事先做好准备,将自己的金币数好并用一个个的小钱 袋装好,以便在他现有金币的支付能力下,任何数目的金币他都能用这些封闭好的小钱的组合来付账。鬼谷子也是一个非常节俭的人,他想方设法使自己在满足上述 要求的前提下,所用的钱袋数最少,并且不有两个钱袋装有相同的大于1的金币数。假设他有m个金币,你能猜到他会用多少个钱袋,并且每个钱袋装多少个金币 吗?
Input
包含一个整数,表示鬼谷子现有的总的金币数目m。其中,1≤m ≤1000000000。
Output
只有一个整数h,表示所用钱袋个数
Sample Input
3
Sample Output
2