codefoces D. Phoenix and Science

原题链接：https://codeforc.es/problemset/problem/1348/D

题意：给你一个体重为一克的细菌（它可以每天进行一次二分裂即一分为二体重均分；晚上体重增加1克）求最快所有细菌体重所达到n克所需最短时间。

题解：不难看出来这题要用到贪心的思想，如果每天所有细菌都进行分裂那么一天增加的体重最大，那么达到n克的天数就越少。构造一个公比是2的等比数列20,21,22,23…2x。

如果sum==n那么x即为答案；如果sum<n，就需要将n-sum加入数组中，同时天数加一。再加上每天分裂细菌数为a[i]-a[i-1]，就可以得到答案。

Ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod1=1e9+7;
const ll mod2=0x3f3f3f3f;
const ll maxn=1e4+5;
int main(){
   int t;
   cin>>t;
   while(t--){
   int n;
   cin>>n;
   vector<int>a;
   int sum=0;
   for(int i=1;sum+i<=n;i*=2){
   sum+=i;
   a.push_back(i);
   }
   if(sum<n) a.push_back(n-sum);
   sort(a.begin(),a.end()); //排序；
   cout<<a.size()-1<<endl;
   //for(std::size_t  i = 0;i<a.size();i++) cout<<a[i]<<" "; 帮助判断每一天需要的分裂的细菌数。
     // cout<<endl;
   for(std::size_t  i = 1;i<a.size();i++){
   cout<<a[i]-a[i-1]<<" ";
   }
   cout<<endl;
   }
return 0;
}