灾祸之一 至尊灾杰·麦哲佩恩

zrzring 2021-01-13 PM 19℃ 0条

题目链接

对原序列差分出来,把区间修改变成单点修改,一字型可以直接得出答案,人字形枚举一个最高点即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e6 + 10, M = 2e6 + 10, inf = 0x3f3f3f3f;

const long long Linf = 0x3f3f3f3f3f3f3f3f;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

int n, m, cnt, pos, neg, ans, l, r, dat[N];

int main() {
    n = read();
    for (int i = 1; i <= n; i++) dat[i] = read(); n--;
    for (int i = 1; i <= n; i++) dat[i] -= dat[i + 1], pos += (dat[i] > 0) * dat[i], neg += (dat[i] < 0) * -dat[i];
    int ans = max(pos, neg);
    for (int i = 2; i <= n; i++) r += (dat[i] <= 0) * (-dat[i] + 1); l = (dat[1] >= 0) * (dat[1] + 1); ans = min(ans, max(l, r));
    for (int i = 2; i <= n; i++) l += (dat[i] >= 0) * (dat[i] + 1), r -= (dat[i] <= 0) * (-dat[i] + 1), ans = min(ans, max(l, r));
    printf("%d", ans);
    return 0;
}
Title - Artist
0:00