P8446 虹色的北斗七星题解

Svemit / 2023-05-06 / 原文

传送门

前言：

很久之前做的一道题目了，当时并没有想出来怎么做，随便猜了个结论交上去发现过了。（~~好像还是第一道自己做出来的绿~~）

简要题意：

你有一个长度为 \(n\) 的序列 \(a\) ，一个区间\([l, r]\)的价值定义为当前区间的极差减去区间长度，求出最大的价值。

\(Solution\)：

看了看题解，发现大多数都是说 \(l, r\) 对应的数字一定是一个最大一个最小，然后枚举其中一个端点。
真的需要大力分讨吗？？？
考虑单调队列的思想（~~当时还没学欸~~），不能用的答案我们就及时排除掉。
假设当前最大值的位置是 \(mxpos\) ，最小是 \(mnpos\) ,最大数最小数分别是 \(mx, mn\)，并且此时遍历到 \(a_i\)，如果 \(a_i < mn\) 的话，那么 \(mn\) 就变成 \(a_i\) ，贡献是很好算的，如果 \(a_i > mn\) 的话，相当于区间长度增加了 \(1\) ，怎么做呢？将 \(mn = mn + 1\)就行了，就等价与贡献减小了 \(1\) ，最大值用相似的方法处理就行了，遍历过程中用

res = max(mx - mn - 1， res);

更新答案即可。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, INF = 1 << 30;
const ll mod = 1e9 + 7;
int n, mn = INF, mx = -INF, res = -1;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for(int i = 1, x;i <= n;i ++)
	{
		cin >> x;
		mn = min(mn + 1, x), mx = max(mx - 1, x);
		res = max(res, mx - mn - 1);
	}
	cout << res;
    return 0;
}