题目描述

题目要求的是将一段波动形数列通过若干次对区间$[l, r]$进行加一或者减一的操作达到数列是一段常数列的要求。

题目样例

• 输入样例

4
1
1
2
2

• 输出样例

1
2

思路

1. 看到这道题首先应当联想到差分的相关知识。对一段区间进行同时加一减一的操作非常像797差分模板题的题目操作，即对数组的一段区间同时加上任意常数c。换言之，这道题的目标转化为使得差分数组$[2, n]$这一段值均为0。

   对数组进行操作的时候，一定要分清楚我们是在对原数组进行操作还是在对原数组的差分数组进行操作。
   1. 对原数组进行的操作是对一段区间$[l, r]$进行加一(减一)
   2. 与之对应的差分数组的操作是对第l项进行加一(减一)，对第r项进行减一(加一)。
   总结一下，就是原数组一段区间的操作一定对应到差分数组两个点的操作。并且第一个点加一代表整个区间加一，反之亦然。

1. 这道题的一个难点就是如何进行最少次数的操作。为了使我们的每一步操作都能最大化发挥作用，在一开始我们应当对差分数组$[2, n]$一个正数p和一个负数q进行配对组合。对于这个组合而言，当p与q中绝对值较小的数消为0，另一个也能更接近于零，这样达到了一石二鸟的效果。对于整体而言，我们第一步的操作就是将所有正数的和pos与所有负数的和neg的绝对值进行比较，对较小的一方消为0.该操作最后的结果都是一样的，所需的操作次数是$min(|pos|, |neg|)$.

1. 接下来就是将差分数组[2, n]所有相同符号的数消为0.根据第一步的探讨，我们知道对原数组的每一次操作都必然会导致差分数组的两项元素的变化。因此对于差分数组[2, n]的变化(比如说将正项变为0，即减一)，我们必须找到一个“替死鬼”来承担与之相反的变化(即加一)。因为差分数组的第$1$项与$n+1$项不会影响最后数组的一致性，故每个操作可以选择这两项的其中之一进行操作。而差分数组的第$1$项其实就是最后原数组的所有元素的值。所以这一步操作次数为$||pos| - |neg||$，可能的情况有$||pos| - |neg|| + 1$的情况。(因为总共操作$||pos| - |neg||$次，可以选择对差分数组第一项进行操作，也可以都不对差分数组第一项操作)

   比如说选择第$1$项进行+1操作相当于原数组$[1, i - 1]$向上移动一个单位；选择第$n + 1$项进行相同的操作则是原数组$[i, n]$向下移动一个单位。

   注意:原数组的第$1$,$n + 1$项是自定义为0.

时间复杂度

• 计算差分数组的时间复杂度是$O(n)$
• 操作的时间复杂度是$O(n)$
  综上，为$O(n)$

C++ 代码

#include <iostream>

typedef long long LL;

using namespace std;

const int N = 1e5 + 10;
LL a[N], b[N], pos, neg;

int main() {
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) {
        scanf("%lld", &a[i]);
        b[i] = a[i] - a[i - 1];
    }

    for(int i = 2; i <= n; ++ i) {
        if(b[i] > 0) pos += b[i];
        else neg -= b[i];
    }

    if(pos >= neg) 
        cout << pos << endl << pos - neg + 1 << endl;
    else
        cout << neg << endl << neg - pos + 1 << endl;

    return 0;
}