题目传送门
因为题意要求,每次都一个区间加上1或者减去1,所以想到了差分。
首先,先对数组\(a\)差分一下,求出差分数组\(b\),接下来我们的任务就是对\(b[2\sim n]\)全部变成\(0\)(所有的数和\(b[1]=a[1]\)一样)即可。
我们对差分序列\(b\)直接操作,因为一个\(++\),一个\(--\),所以我们在\(2 \sim n\)之间要选择一个正数一个负数,一个\(--\),一个\(++\),这样就可以尽可能较少操作步骤,剩下的就和\(b[1]\)或者\(b[n+1]\)抵消(不影响整体结果)。
\(p\)为\(b\)当中正数的和。
\(q\)为\(b\)当中负数绝对值的和。
操作步骤\(=min(p,q)+abs(p-q)\)
因为最后可以选择\(b[1]\)或者\(b[n+1]\)抵消,
比如\(b=1 0 2 0\)
它可以有
\(3 0 0 0\)(全部和\(b[1]\)消除)
\(2 0 0 0\) (一个\(b[1]\),一个\(b[n+1]\))
\(1 0 0 0\)(全部\(b[n+1]\))
结果数量=\(abs(p-q)+1\)
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 100010; int n; int a[N], b[N]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = a[i] - a[i - 1]; } LL p = 0, q = 0; for (int i = 2; i <= n; i++) if (b[i] > 0) p += b[i]; else q -= b[i]; printf("%lld\n%lld\n", max(p, q), abs(p - q) + 1); return 0; }