P2320 [HNOI2006]鬼谷子的钱袋

3

2
1  2

我想说这题的第一问也就是需要多少钱袋，可以o(1)的时间做出来，取log2(n)+1就好，因为这个题是在二进制的基础上运算的

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 using namespace std;
 5 const int MAXN=10000000;
 6 int wallet[MAXN];
 7 int num=1,i;
 8 int main()
 9 {
10     int n;
11     scanf("%d",&n);
12     printf("%d\n",(int)log2(n)+1);
13     for(i=1;i<=n;i=i*2)
14     wallet[num++]=i,n-=i;
15     if(n>0)wallet[num++]=n;
16     sort(wallet+1,wallet+num);
17     for(int i=1;i<num-1;i++)
18         if(wallet[i]==wallet[i+1]&&wallet[i]!=1)
19         wallet[i]--,wallet[i+1]++;
20     for(int i=1;i<=num-1;i++)
21         printf("%d ",wallet[i]);
22     return 0;
23 }