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

正解:找规律?或者,这个算分治嘛?

 

分析:刚开始定性思维分解成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 }