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

題目大意：給出一個(gè)由 n 個(gè)數(shù)組成的數(shù)列 a，選擇一個(gè)最小的 k ，代表可以進(jìn)行 k 次操作，對(duì)于第 t 次操作可以選擇任意個(gè)位置使得 a[ i ] = a[ i ] + 2^( t?- 1 )，問最少需要多少次操作才能使序列滿足非嚴(yán)格遞增

題目分析：讀完題后的第一反應(yīng)是模擬+貪心，實(shí)際上不是的，需要想到的一個(gè)知識(shí)點(diǎn)是，任何數(shù)字都可以用二進(jìn)制來(lái)表示，相應(yīng)的題目中的操作可以轉(zhuǎn)換為二進(jìn)制加法，進(jìn)而轉(zhuǎn)換為：對(duì)于某個(gè)位置，都可以加上任何一個(gè)數(shù)

因?yàn)樾枰屨麄€(gè)序列非嚴(yán)格遞增，所以取任意兩個(gè)位置 i 和 j 滿足 i < j 討論一下：

如果 a[ i ] <= a[ j ] ：顯然已經(jīng)滿足題目要求，無(wú)需操作

如果 a[ i ] > a[ j ] ：讓 a[ j ] 加上一個(gè)數(shù)變?yōu)?a[ i ] 顯然是最優(yōu)的

這樣一來(lái)我們只需要維護(hù)一下前綴的最大值，對(duì)于后續(xù)的每個(gè) a[ i ] ，找出最大的差值就好了

代碼：

#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);int mmax=-inf,dif=-inf;for(int i=1;i<=n;i++){int num;scanf("%d",&num);mmax=max(mmax,num);dif=max(dif,mmax-num);}int ans=0;while((1LL<<ans)-1<dif)ans++;printf("%d\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1339C Powered Addition(思维+贪心)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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