目录
显示
题目链接
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; }