Codeforces Round 890 (Div. 2)
A. Tales of a Sort
题意给定一段数字序列，每次操作将每个大于 \(0\) 的数 \(-1\) ，求最少几次操作后整个序列单调上升。我们可以转化成将序列中的每个数都减去某个数 \(x\) ， 使得序列大于等于 \(0\) 的部分单调上升，这个 \(x\) 就是操作的次数。也就是说 \(x\) 满足：序列中大于等于 \(x\) 的数单调上升，且 \(x\) 最小。并且容易发现序列最大值一定在这个区间中。到这里我们已经有了一个 \(O(nlongA)\) 的做法：二分 \(x\) 的值再遍历检查。不过还可以优化。我们可以把这段序列在平面上表示出来： x轴代表第几个数，y轴代表数的大小，描点后连线起来，于是整个序列的大小变化就成了波谷和波峰。然后只看大于 \(x\) 的部分，会发现这个部分的形状是从 \(f(x) = x\) 的直线然后从某个点开始向上至第 \(n\) 个数结束。因此我们的做法就是从 \(n\) 开始从后往前遍历数组，若 \(a_i > a_{i - 1}\) , 那么在从 \(a_1 - a_i\) 找出最大值就是 \(x\) 。 \(O(n)\) 复杂度。
code:
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define N 60
int a[N];
signed main(){
// freopen("shuju.in", "r", stdin);
// freopen("shuju.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
int flag = 1;
for(int i = n - 1; i >= 1; i --){
if(a[i] > a[i + 1]){
int ans = 0;
for(int j = 1; j <= i; j ++){
ans = max(ans, a[j]);
}
cout << ans << endl;
flag = 0;
break;
}
}
if(flag) cout << 0 << endl;
}
}