做法和二进制划分很像,,, 原来我的二进制划分一直有点问题 (之前我是枚举 2 的 n 次方然后减, 逃)...
我们举 20 这个例子, 假如我们要表示 20 以内的数, 那么一定要取 10, 然后再表示出 1 到 10 之内的数, 加上 10 也就表示出了 11 到 20 之内的数. 同理, 不断往下推, 我们发现将 m 不断二分, 每次得到的结果一定可以表示 m 以内的数, 还可以使得用来表示的数最少, 大约是 log(m).
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- int a[35],cnt;
- int main() {
- int n;
- scanf("%d",&n);
- while(n) {
- a[++cnt]=n%2==0?n/2:n/2+1;
- n/=2;
- }
- printf("%d\n",cnt);
- sort(a+1,a+cnt+1);
- for(int i=1;i<=cnt;++i) {
- if(i!=1) putchar(' ');
- printf("%d",a[i]);
- }
- return 0;
- }
AC 代码
来源: http://www.bubuko.com/infodetail-2790571.html