[洛谷 2320][HNOI2006]鬼谷子的钱袋

题目链接

https://www.luogu.org/problem/P2320

题解

这道题第一问显然有些二进制的味道啊，比如说我们想要组成 \(7\) 的话：\(7=4+2+1\)，这么加起来不就能组成 \(7\) 了吗！

上面的这三个数字不仅能组成 \(7\)，甚至还能组成 \( 1 \ldots 7\) 的所有数字。

于是答案是 \(3\)，而 \(7\) 的二进制位数也是 \(3\)。

这时肯定有人要提出疑问了，假如是 \(8\) 呢？

那么 \(8=4+2+1+1\)，结果需要 \(4\) 个钱袋，而 \(8\) 的二进制位数为 \(4\)。

回想一下整数的二进制拆分，本题的答案确实是：\( \log_2 m +1\)（说白了，就是 \(m\) 的二进制位数）。

至于第二问，和上面一样采用二进制拆分就可以了。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int a[105];
int main()
{
 int m,cnt=0;
 scanf("%d",&m);
 printf("%d\n",(int)log2(m)+1);
 while(m>0)
 {
  if(m%2)a[++cnt]=m/2+1;
  else a[++cnt]=m/2;
  m/=2;
 }
 sort(a+1,a+cnt+1);
 for(int i=1;i<=cnt;i++)
  printf("%d ",a[i]);
 return 0;
}