洛谷 P4552 [Poetize6] IncDec Sequence （进阶指南， 差分数组）

算法竞赛进阶指南，23页， 差分数组
本题要点：
1、数组 a[i] 有n个数， 数组b[i] 是 a数组的差分数组， 并且 b[n + 1] = 0;
数组 b 中任意选两个数 b[i] 和 b[j] （一个加1， 一个减1）， 分为4 类：
1） 2 <= i, j <= n; //这种情况，一正一负，尽量选择这种操作， 能更快地使得每个 b[i] 都变成 0
2） i == 1 , 2 <= j <= n
3） i == n + 1 , 2 <= j <= n
4） i == 1 , j == n + 1, //这种操作是没有意义的
2、p, q 分别是差分数组 b[2] ~ b[n] 的 所有正数的和, 负数的绝对值的和；
首先正负配对，有 min(p, q) 次操作， 也就是第1类操作；剩下 |p - q| 个未配对；
接下来执行 |p - q| 次 2 或 3 类操作； 最少的操作次数为 min(p, q) + |p - q| = max(p, q);
|p - q| 次 2 或 3 类操作, 能产生 |p - q| + 1 个不同 的b[1] 值，也就是 |p - q| + 1 个不同的结果
3、 使用 long long

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MaxN = 100010;
int n;
LL a[MaxN], b[MaxN];

void solve()
{
	LL p = 0, q = 0;	//分别是差分数组 b[2] ~ b[n] 的 所有正数的和, 负数的绝对值的和
	a[0] = 0;
	b[1] = a[1];
	b[n + 1] = 0;
	for(int i = 2; i <= n; ++i)
	{
		b[i] = a[i] - a[i - 1];
		if(b[i] >= 0)
		{
			p += b[i];
		}else{
			q -= b[i];
		}
	}
	printf("%lld\n", max(p, q));
	printf("%lld\n", abs(p - q) + 1);
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
	{
		scanf("%lld", &a[i]);
	}
	solve();
	return 0;
}

/*
4
1
1
2
2
*/

/*
1
2
*/