題目描述
http://codeforces.com/contest/1339/problem/C
給定一個長度為 \(n\) 的無序陣列，你可以在第 \(x\) 秒進行一次下面的操作，
- 從陣列選取任意個數字（也可以一個都不選），為他們全部都加上 \(2^{x-1}\) ，
詢問你最少可以用多少秒，使得陣列非降序排列，
解題
最快策略
首先簡化一下問題，假設操作變成：第 \(x\) 秒，可以選取任意個數字，為他們全部都加上 \(1\) ，分析一下在這個條件下，可以達到最少秒數的策略，
- 假設我們有一個分布如下圖的不規則序列，
- 最快的讓這個序列非降序排列的填充方案如圖，
設對數字 \(a_i\) 加 \(1\) 的次數為 \(d_i\)，可以不難發現 \(d_i = max\{a_j|j\le i\} - a_i\) ，又因為每次 \(+1\) 操作是批量的，即每次可以選取多個 \(a_i\) 進行 \(+1\) 操作，所以最快策略的秒數花費 \(ans = max\{d_i|i\in[1,n]\}\) ，
最終解題
同理，設對數字 \(a_i\) 加 \(2^{x-1}\) 的操作次數為 \(d_i\)，
\[d_i = \left\{ \begin{array}{**lr**} sovle("max\{a_j|j\le i\} - a_i = \sum _{k=1}^{d_i}2^{k-1}")& ,max\{a_j|j\le i\} - a_i\gt 0\\\\ 0& ,max\{a_j|j\le i\} - a_i= 0\\ \end{array} \right. \]
最后結果 \(ans = max\{d_i|i\in [1,n]\}\) ，
#include<bits/stdc++.h>
#define ll long long
#define fr(i,n) for(int i=0;i<n;i++)
#define frs(i,n,flag) for(int i=0;i<n&&flag;i++)
#define frr(i,j,n) for(int i=j;i<n;i++)
#define r_frr(i,j,n) for(int i=n-1;i>=j;i--)
#define frrs(i,j,n,flag) for(int i=j;i<n&&flag;i++)
#define r_frrs(i,j,n,flag) for(int i=n-1;i>=j&&flag;i--)
#define arend(i,n) ((i!=n-1)?" ":"\n")
#define memset0(dp) memset(dp,0,sizeof(dp))
#define print_arr(begin,end) for(auto it = begin;it!=end;it++) cout<<*it<<arend(it,end);
#define log_this(name,value) cout<<name<<": "<<value<<endl;
#define e4 10004
#define e5 100005
#define e6 1000006
#define e7 10000007
#define e9 1000000000
#define INF 9999999
using namespace std;
int to_int(string s) {stringstream ss;ss<<s;int a;ss>>a;return a;}
string to_str(double a) {stringstream ss;ss<<a;return ss.str();}
ll a[1*e5];
int main(){
cin.tie(0);
//ios::sync_with_stdio(false);
//cout<<setiosflags(ios::fixed)<<setprecision(0);
//freopen("1.out","w",stdout);
int t;
while(cin>>t){
while(t--){
int n;
cin>>n;
fr(i,n){
cin>>a[i];
}
ll pr = 0;
ll maxa = a[0];
fr(i,n-1){
maxa = max(maxa,a[i+1]);
pr = max(pr,maxa-a[i+1]);
}
ll x = 0;
ll pw = 1;
while(pr>0){
pr -= pw;
pw *= 2;
x++;
}
cout<<x<<endl;
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/62077.html
標籤：其他
上一篇：資料結構-插入排序法
下一篇：Codeforces Round #633 (div.2) B. Sorted Adjacent Differences