题意

每次给一个区间整体加一或减一，求把序列变成常数序列的最少操作数，以及最少操作下可能的最终常数个数。

思路

只看相邻差 a[i]-a[i-1]。设所有正差之和为 positive，所有负差绝对值之和为 negative。一次操作最多同时消去一份正差和一份负差，剩余部分再与序列外侧配对，因此最少操作是两者最大值。

未配对的 abs(positive-negative) 份操作可以分配到左右边界，最终常数共有 abs(positive-negative)+1 种。

Python 知识

• pairwise(sequence) 直接产生所有相邻元素对。
• 两个生成器分别求正向、负向变化量，公式与代码一一对应。
• Python 整数自动扩容，不需要 C++ 的 long long 类型选择。

代码

1
2
3
4
5
6
7
8
9
10
11import sys
from itertools import pairwise


data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
sequence = [next(data) for _ in range(n)]
positive = sum(max(0, right - left) for left, right in pairwise(sequence))
negative = sum(max(0, left - right) for left, right in pairwise(sequence))
print(max(positive, negative))
print(abs(positive - negative) + 1)

复杂度

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

总结

区间整体变化在差分数组中只影响边界，问题最终只剩正负变化量如何配对。