P2320鬼谷子的钱袋(分治)

------------恢复内容开始------------

描述:https://www.luogu.com.cn/problem/P2320

m个金币，装进一些钱袋。钱袋中大于1的钱互不相同。

问最少需要几个钱袋，能使任意小于m的金币数表示出来。

---

比如一个数是20，那么我们如何表示从1到20所有的数呢？

假设我们能表示1~10的金币数，是不是只要再来一个金币数为10的袋子，就能表示11~20的金币

那我们能表示1~5，再来一个金币为5的袋子就行了。

以此类推。

那为什么要往中间分开呢？

我我们来试一试，如果获得了1~9，来一个金币数为11的袋子，很容易发现10是表示不出来的。

所以二分才是合理的，这样定义可以解决问题。

但二分的时候遇到奇数怎么办呢?比如我们要获得1~3

如果直接二分，那我们需要3/2=1个金币的袋子

并且剩下来只需要再获得3/2=1个金币

所以正确的做法应该是向上取整，需要(3+1)/2=2个金币

#include <bits/stdc++.h>
using namespace std;
int n,f[10000],cnt=1;
int main()
{
    cin>>n;
    while(n)
    {
        f[cnt++]=(n+1)/2;
        n/=2;
    }
    cout<<cnt-1<<endl;
    for(int i=cnt-1;i>=1;i--)
        cout<<f[i]<<" ";
}

------------恢复内容结束------------