- Time Limit: 10 Sec Memory Limit: 162 MB
- Submit: 5214 Solved: 3581
- [Submit][Status][Discuss https://www.lydsy.com/JudgeOnline/bbs.PHP?id=1192 ]
- Description
鬼谷子非常聪明, 正因为这样, 他非常繁忙, 经常有各诸侯车的特派员前来向他咨询时政. 有一天, 他在咸阳游历的时候, 朋友告诉他在咸阳最大的拍卖行 (聚宝商行) 将要举行一场拍卖会, 其中有一件宝物引起了他极大的兴趣, 那就是无字天书. 但是, 他的行程安排得很满, 他他已经买好了去邯郸的长途马车标, 不巧的是出发时间是在拍卖会快要结束的时候. 于是, 他决定事先做好准备, 将自己的金币数好并用一个个的小钱袋装好, 以便在他现有金币的支付能力下, 任何数目的金币他都能用这些封闭好的小钱的组合来付账. 鬼谷子也是一个非常节俭的人, 他想方设法使自己在满足上述要求的前提下, 所用的钱袋数最少, 并且不有两个钱袋装有相同的大于 1 的金币数. 假设他有 m 个金币, 你能猜到他会用多少个钱袋, 并且每个钱袋装多少个金币吗?
Input
包含一个整数, 表示鬼谷子现有的总的金币数目 m. 其中, 1≤m ≤1000000000.
Output
只有一个整数 h, 表示所用钱袋个数
- Sample Input
- 3
- Sample Output
- 2
题解:
把整数 m 拆分成 h 份, 要求 h 的子集和可以表示所有小于等于 m 的整数
利用了多重背包二进制优化中的思想: 1,2,4,8 ,16 , 32......2^n 可以组成从 1 到 2^(n+1)-1 中的任何数
1+2+4+......+2^n = 2^(n+1)-1
所以就是求最小的 n,st.(1 <<n)-1 >= m
- #include <bits/stdc++.h>
- using namespace std;
- int m;
- int main(){
- int k = 1;
- scanf("%d",&m);
- while((1 << k)-1 < m) k++;
- printf("%d\n",k);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2797999.html