【贪心】D – Phoenix and Science

D - Phoenix and Science

题意：初始有1个质量为1的细菌，每次可以选任意个细菌进行分裂，分裂后所得的两个细菌质量均为原细菌的一半。选完之后现有全部细菌质量+1。问最少操作几次可以使得细菌总质量为n。

思路：

简化题意：设第\(k\)次操作后细菌总质量为\(sum\)，细菌数为\(x\)，则第\(k+1\)次细菌总质量的增量在\([x,2x]\)范围内。也就是说，给定\(x=1,sum=1\),每次可任选\([x,2x]\)范围内的一个整数加上sum，问最少加几次能使sum=n

按照贪心思想，每次都应取最大值\(2x\)，但这可能导致最后一次加上\(2x\)后\(sum>n\)，设此时的\(d=sum-n\)，把这个\(d\)插入到能使\(d\)满足\([x,2x]\)的那一天去加就可以了。

注意数组记录的是每次操作结束后的\(sum\)，所以需要差分一下输出答案

void solve() {
    int n;
    cin >> n;//要到达的数量
    vector<int> v;
    int x = 1;
    while (n > 0) {
        if (n > x) v.push_back(x);//每一次都取全部繁殖
        else v.push_back(n);//如果全部繁殖会超，就取都不繁殖
        n -= x;
        x *= 2;
    }
    sort(v.begin(), v.end());
    cout << v.size() - 1 << endl;
    for (int i = 1; i < v.size(); i++) cout << v[i] - v[i - 1] << " ";
    cout << endl;
}