2026/4/3 【春假提高思维测试】H. 增减序列

洛谷原题：P7404 [JOI 2021 Final] 有趣的家庭菜园 4 / Growing Vegetables is Fun 4

思路

由题可知，操作完后序列 \(A\) 的前半段为严格递增序列，后半段为严格递减序列。因此考虑使用差分。

• 定义：
  • \(d_i=a_i-a_{i-1}\)，
  • \(pre_i\) 表示区间 \([1..i]\) 严格递增所需的最少操作数量，
  • \(suf_i\) 表示区间 \((i..n]\) 严格递增所需的最少操作数量。
• 转移方程：
  • \(pre_i=\begin{cases}pre_{i-1}+|d_i|+1&d_i\le0\\pre_{i-1}&d_i>0\end{cases}\)
  • \(suf_i=\begin{cases}suf_{i+1}+d_i+1&d_i\ge0\\suf_{i+1}&d_i<0\end{cases}\)
• 答案：\(ans=\min_{i=1}^n\{\max\{pre_i,suf_{i+1}\}\}\)

代码

#include <bits/stdc++.h>
using namespace std;
int n, a[200005], d[200005];
long long pre[200005], suf[200005], ans = 9e18;
int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> a[i], d[i] = a[i] - a[i - 1];for (int i = 2, j = n; j; i++, j--) {pre[i] = pre[i - 1], suf[j] = suf[j + 1];if (d[i] <= 0) pre[i] += -d[i] + 1;if (d[j] >= 0) suf[j] += d[j] + 1;}for (int i = 1; i <= n; i++)ans = min(ans, max(pre[i], suf[i + 1]));cout << ans;return 0;
}

记得开 long long。