P8446 虹色的北斗七星 题解

· · 题解

cnblogs

传送门

前言：

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

简要题意：

你有一个长度为 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;
}