題目鏈接：點(diǎn)擊查看

題目大意：起始時有一個細(xì)菌，質(zhì)量為 1 ，每個白天可以選擇數(shù)個細(xì)菌進(jìn)行分裂，可以是 0 個，也可以是全部，然后每個晚上所有細(xì)菌的質(zhì)量加一，問最少需要多少天所有細(xì)菌的總和可以達(dá)到 n ，給出一種構(gòu)造方案

題目分析：比賽的時候拉胯了，這個題和 C 題都沒想出來，感覺自己的紫名名不副實(shí)（給紫名丟人了真的對不起orz），不過還好打的是小號，說好聽點(diǎn)就叫戰(zhàn)略性掉分吧

貪心，首先需要get到出題人想考察的是二進(jìn)制，其次是沒有 -1 的情況，這個應(yīng)該不難看出來，因?yàn)槿绻环至?#xff0c;那么到第 n 天質(zhì)量肯定可以到達(dá) n 的，那么目標(biāo)就是需要求出最少的分裂天數(shù)，使得滿足條件

滿足什么條件呢？不難看出最后的總質(zhì)量與細(xì)菌每天的數(shù)量相關(guān)，所以我們設(shè) a[ i ] 為第 i 天時的細(xì)菌數(shù)量，那么顯然答案就是 1 + a[ 1 ] + a[ 2 ] + a[ 3 ] .... + a[ k ] ，k 為最小天數(shù)，再考慮一下兩種極限情況：

1 1 1 1 1 1 1 1..... 1 1 1 1 1，對應(yīng)著細(xì)胞不分裂，只增加質(zhì)量，第 i 天至少能到達(dá) i 的質(zhì)量

1 2 4 8 16 32 ...... 2^k，對應(yīng)著每天所有細(xì)胞都分裂，第 i 天至多能到達(dá) 2^i - 1 的質(zhì)量

這樣我們只需要貪心分裂就行了，前面的 1 2 4 8 等等等能分裂就分裂，最后剩下一個數(shù) remain ，也就是還差著 remain 的質(zhì)量，我們將其插入到前面的序列中就行了，假設(shè) 4 <= remain <= 8 的話，序列就變成了 1 2 4 remain 8 16 .... 2^k 了，顯然質(zhì)量總和為 n，且 a 數(shù)組滿足升序，接下來只需要將其轉(zhuǎn)換為題目要求的格式就行了，題目需要我們輸出的是每天有多少個細(xì)菌分裂，顯然就是數(shù)組 a 的差分?jǐn)?shù)組了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n;scanf("%d",&n);vector<int>ans;for(int i=1;i<=n;i<<=1){ans.push_back(i);n-=i;}if(n)ans.push_back(n);sort(ans.begin(),ans.end());printf("%d\n",ans.size()-1);for(int i=0;i<ans.size()-1;i++)printf("%d ",ans[i+1]-ans[i]);puts("");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1348D Phoenix and Science(贪心)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。