[洛谷 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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注