题目

调整数组

题目描述

给定一个长为 N 的正整数数组 A，下标从 1 开始，你可以进行 0 次或任意正整数次下面这种操作：

• 选取一个子段 [A_L, ..., A_R] ，让这个子段中的每个数同时加 1。

求让数组 A 能够满足下面要求的最小操作次数：

• 存在一个整数 k \in [1,N]，满足 A_1 < ... < A_k > A_{k + 1} > ... > A_N

特殊地：

• 当 N = 1 时，A 数组一定会满足要求
• 如果 k = 1，则该要求为 A_1 > ... > A_N
• 如果 k = N，则该要求为 A_1 < ... < A_N

输入格式

第一行，包含一个正整数 N

第二行，包含 N 个正整数 A_i

输出格式

输出一行，包含一个非负整数，表示答案

样例 #1

样例输入 #1

5
3 2 2 3 1

样例输出 #1

3

样例 #2

样例输入 #2

5
9 7 5 3 1

样例输出 #2

0

样例 #3

样例输入 #3

2
2024 2024

样例输出 #3

1

样例 #4

样例输入 #4

8
12 2 34 85 4 91 29 85

样例输出 #4

93

提示

数据范围

子任务 1（40 分）：1 \leq N \leq 2000

子任务 2（60 分）：1 \leq N \leq 2 \times 10^5

对于全部数据，1 \leq N \leq 2 \times 10^5, 1 \leq A_i \leq 10^9

题解

1. 作者在前面的话：这题是很普及组的题，就是稍微考验一点思维，但是作者可能是写题少了的缘故挂分了
2. 代码是我写的，文章没空写给AI(chat-o1-mini)写了

解题思路

题目要求通过对数组进行特定的加1操作，使得数组中存在一个转折点 k，满足 A_1 < A_2 < ... < A_k > A_{k+1} > ... > A_N。为了达到这一目标，关键在于合理地选择操作的子段，并最小化操作次数。

操作解析

每次操作可以选择一个子段 [A_L, ..., A_R]，让该子段中的所有元素同时加1。要使得最终数组满足单调递增到 k，再单调递减的要求，可以转化为以下步骤：

1. 差分数组：构造差分数组 d[i] = A[i] - A[i-1]（对于 i = 1，A[0] 可视为0）。为了实现递增到 k，需保证 d[2], d[3], ..., d[k] > 0；为了实现从 k 开始递减，需保证 d[k+1], d[k+2], ..., d[N] < 0。

2. 前缀调整：对于每个位置 i，计算将 d[1] 到 d[i] 调整为正所需的最小操作次数 p[i]。

3. 后缀调整：对于每个位置 i，计算将 d[i] 到 d[N] 调整为负所需的最小操作次数 s[i]。

4. 综合考虑：对于每个可能的转折点 k，需要 p[k] 和 s[k+1] 都满足，故对于每个 k，操作次数为 max(p[k], s[k+1])。最终的答案是所有可能 k 的最小值。

代码注释

#include <bits/stdc++.h>

using ll = int64_t;
using namespace std;

const ll maxn = 2e5 + 5, inf = (1LL << 60);
ll n, a[maxn], d[maxn], p[maxn], s[maxn];
ll ans = inf;

// 辅助函数，用于输出数组（调试用）
template<class T>
void pa(T *t){
    for(ll i = 1; i <= n; i++) cout << t[i] << ' ';
    cout << '\n';
}
template<class T, class ...Args>
void pa(T&&t, Args&&...args){
    pa(t);
    pa(args...);
}

int main(){
    // 加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for(ll i = 1; i <= n; i++) cin >> a[i];
    
    // 计算差分数组 d[i] = A[i] - A[i-1]
    for(ll i = 1; i <= n; i++){
        d[i] = a[i] - a[i-1];
        if(d[i] <= 0){
            // 如果差分非正，需要调整为至少1
            // 调整次数为 (1 - d[i])
            p[i] = p[i-1] + 1 - d[i];
        }
        else{
            // 差分已经为正，无需调整
            p[i] = p[i-1];
        }
    }
    
    // 从后往前计算将差分调整为负所需的操作次数
    for(ll i = n; i >= 1; i--){
        if(d[i] >= 0){
            // 如果差分非负，需要调整为至少-1
            // 调整次数为 (d[i] + 1)
            s[i] = s[i+1] + d[i] + 1;
        }
        else{
            // 差分已经为负，无需调整
            s[i] = s[i+1];
        }
    }
    
    // 遍历所有可能的转折点 k，计算最小的操作次数
    for(ll i = 1; i <= n; i++){
        /*
            对于每个转折点 k = i，
            需要前缀 [1, k] 调整为递增，后缀 [k+1, N] 调整为递减
            因为操作可以重叠，因此取 p[k] 和 s[k+1] 的最大值
        */
        ans = min(ans, max(p[i], s[i+1]));
    }
    
    cout << ans << '\n';
}

详细解释

1. 差分数组的构造：

   • 差分数组 d[i] = A[i] - A[i-1] 表示相邻元素之间的差值。为了使数组在某个点 k 前单调递增，需要 d[2] > 0, d[3] > 0, ..., d[k] > 0；在 k 后单调递减，需要 d[k+1] < 0, d[k+2] < 0, ..., d[N] < 0。

2. 前缀操作次数 p[i]：

   • 遍历数组，从左到右计算前缀中每个差分需要调整为正的最小操作次数。
   • 若 d[i] > 0，不需要调整，p[i] = p[i-1]。
   • 若 d[i] <= 0，需要将其至少调整为1，操作次数增加 1 - d[i]。

3. 后缀操作次数 s[i]：

   • 从右向左遍历数组，计算后缀中每个差分需要调整为负的最小操作次数。
   • 若 d[i] < 0，不需要调整，s[i] = s[i+1]。
   • 若 d[i] >= 0，需要将其至少调整为-1，操作次数增加 d[i] + 1。

4. 选择转折点 k：

   • 对于每个可能的转折点 k，所需的总操作次数为 max(p[k], s[k+1])。
   • 因为操作可以在前缀和后缀之间重叠，取两者的最大值即可。
   • 最终答案为所有可能 k 的最小值。

总结

该解法通过构造差分数组，将问题转化为调整差分为正和负的最小操作次数问题。利用前缀和后缀的方法，分别计算在不同转折点 k 下所需的操作次数，最终取最小值作为答案。这种方法的时间复杂度为 O(N)，适用于较大的数据规模（最大 N = 2e5）。