题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(3\leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$，下标从$0$ 开始。

每次操作，你可以把$a$中的一个数增加一。

你需要让尽量多的下标在$[1,n-2]$中的数，满足$a[i] \gt a[i-1]$且$a[i] \gt a[i+1]$。

首先，你需要最大化满足上述要求的数的个数；其次，你需要最小化操作次数。输出最小操作次数。

输入样例

6
3
2 1 2
5
1 2 1 4 3
6
3 1 4 5 5 2
8
4 2 1 3 5 3 6 1
6
1 10 1 1 10 1
8
1 10 11 1 10 11 10 1

输出样例

2
0
3
3
0
4

算法

枚举

由于需要满足$a[i] \gt max(a[i-1],a[i+1])$的位置尽可能多，所以根本就没有几种情况，直接枚举：

1. 如果$n$是奇数，那最优解就是从$1$开始，每隔一个位置就满足$a[i] \gt max(a[i-1],a[i+1])$。
2. 如果$n$是偶数，有$3$种情况：$(1)$ 从$1$开始往后，每隔一个位置满足$a[i] \gt max(a[i-1],a[i+1])$；$(2)$ 从$n-2$开始往前，每隔一个位置满足$a[i] \gt max(a[i-1],a[i+1])$；$(3)$ 或者其中有相邻的两个满足$a[i] \gt max(a[i-1],a[i+1])$的位置$i$和$j$，但它们中间隔了$2$个元素，这种情况可以前后缀分解来做（预处理出$l$和$r$两个数组，$l[i]$表示前缀$[0,i]$中从$1$开始每隔一个位置就满足$a[i] \gt max(a[i-1],a[i+1])$的最小操作数，$r[i]$表示后缀$[i,n-1]$中从$n-2$开始每隔一个位置就满足$a[i] \gt max(a[i-1],a[i+1])$的最小操作数），维护$min(l[i]+r[i+3],l[j-3]+r[j])$的最小值即可。

复杂度分析

时间复杂度

$n$为奇数的时候遍历一次数组就能得到答案，$n$为偶数的时候遍历$4$次数组就能得到答案。因此，算法的时间复杂度为$O(n)$。

空间复杂度

当$n$为奇数的时候需要开辟$l$和$r$两个数组空间，它们的空间都是原数组的规模，因此额外空间复杂度也为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 200010;
int T, n, a[N];
LL l[N], r[N];

LL solve() {
    LL ans = 0;
    if(n&1) {
        for(int i = 1; i < n; i += 2) {
            if(a[i] <= max(a[i - 1], a[i + 1])) {
                ans += max(a[i - 1], a[i + 1]) + 1 - a[i];
            }
        }
    }else {
        for(int i = 0; i < n + 5; i++) {
            l[i] = r[i] = 0;
        }
        LL t1 = 0, t2 = 0;
        for(int i = 1; i < n - 1; i += 2) {
            if(a[i] <= max(a[i - 1], a[i + 1])) {
                t1 += max(a[i - 1], a[i + 1]) + 1 - a[i];
            }
            l[i] = t1;
        }
        for(int i = n - 2; i >= 2; i -= 2) {
            if(a[i] <= max(a[i - 1], a[i + 1])) {
                t2 += max(a[i - 1], a[i + 1]) + 1 - a[i];
            }
            r[i] = t2;
        }
        ans = min(t1, t2);
        for(int i = 1, j = n - 2; i < n - 1, j >= 2; i += 2, j -= 2) {
            ans = min(ans, l[i] + r[i + 3]);
            ans = min(ans, l[j - 3] + r[j]);
        }
    }
    return ans;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        printf("%lld\n", solve());
    }
    return 0;
}