AcWing 100. IncDec序列

题目链接：传送门

将序列转化成差分数列
那么题目就变成了对一个数组可进行三种操作
对两个元素一个加一一个减一或对一个元素加一或对一个元素减一
其实后面两种操作实质是对一个元素和队首或队尾进行操作
求最少的操作数使数组所有元素变成$0$0，贪心即可
$f1$f1累计所有正数和，$f2$f2累计所有负数和
$min(f1,f2)$min(f1,f2)抵消掉一部分，$abs(f1-f2)$abs(f1−f2)处理剩下的
$min(f1,f2)+abs(f1-f2)$min(f1,f2)+abs(f1−f2)就是最小的操作数
最终的序列有$abs(f1-f2)+1$abs(f1−f2)+1种
因为还剩下的$abs(f1-f2)$abs(f1−f2)种操作是对队尾或队首的操作
队尾或队首就会影响这个数列的值，所以最多加那么多次，最少一种

#include <bits/stdc++.h>

using namespace std;
int n, a[100010]; long long f1, f2;

int main(int argc, char const *argv[]) {
	cin >> n;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 2; i <= n; i++) {int x = a[i] - a[i - 1]; x > 0 ? f1 += x : f2 -= x;}
	cout << min(f1, f2) + abs(f1 - f2) << endl << abs(f1 - f2) + 1 << endl;
}