P23 差分
求a数组的查分数组,令b[1] = a[1], b[i] = a[i] - a[i-1]
我们每次要进行的操作就是在b[2] ~ b[n]中选择两个数,一个+1一个-1,最终使得b[2] ~ b[n]都为0
我们每次可以进行三种操作:
1. 选择b[2] ~ b[n]之间的两个数,会改变两个数的值
2. 选择b[1]和b[j],会改变b[1]的值
3. 选择b[n+1]和b[j],会改变b[j]的值
4. 对于选择b[1]和b[n+1],因为没有改变b[2] ~ b[n]之间的值,相当于浪费了一次操作,所以肯定不是最优解
实现方法:
求b[2] ~ b[n]的正数总和p和负数总和q。对于min(p, q)之间的值,我们肯定优先执行第1种操作。对于剩下的|p-q|个操作,我们可以选择第2和第3类操作。
所以,总的操作数为min(p, q) + |p - q| = max(p, q)种,一共可以得出|p-q| + 1种b[1]的值,所以不同的结果数就是|p - q | + 1
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
int b[maxn];
signed main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (i > 1) b[i] = a[i] - a[i-1];
else b[i] = a[i];
}
int p = 0, q = 0;
for (int i = 2; i <= n; i++) {
if (b[i] > 0) p += b[i];
else q += -b[i];
}
cout << max(p, q) << "\n";
cout << abs(p - q) + 1 << "\n";
}