不知道为什么巨佬会把这道题加到咱的列表里来...

正解：找规律？或者，这个算分治嘛？

 

分析：刚开始定性思维分解成1,2,4,8,16,32……不够的话补1

　　　然而发现当n=5时就不对了，进一步分析：

　　　对于一个数字，比如说20。

　　

　　　怎么凑20呢？

 　　　方法              ——>          确定的数列

　　　10+10；　　　　　　　　10

　　　5+5　　　　　　　　　　5,10

　　　2+3　　　　　　　　　　3,5,10

　　　1+1　　　　　　　　　　1,3,5,10

　　　1　　　　　　　　　　　1,1,3,5,10

然后下面的核心代码就显然了（洛谷上要求输出方案，这里就记录方案了）：

1 while(n){
2     a[++tot]=n+1>>1;
3     n>>=1;
4 }

 

总代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define int long long
 6 using namespace std;
 7 inline int read(){
 8     char chr=getchar();    int f=1,ans=0;
 9     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
10     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
11     return ans*f;
12 }void write(int x){
13     if(x<0) putchar('-'),x=-x;
14     if(x>9) write(x/10);
15     putchar(x%10+'0');
16 }int n=read(),a[10005],tot;
17 signed main(){
18     while(n){
19         a[++tot]=n+1>>1;
20         n>>=1;
21     }cout<<tot<<endl;//for(int i=tot;i>=1;i--) cout<<a[i]<<" ";
22     return 0;
23 }