P4552-[Poetize6]IncDec Sequence【差分】

正题

题目链接:https://www.luogu.com.cn/problem/P4552

---

题目大意

给出 n n n个数，每次可以选择一个区间加一或减一，求最少操作使得所有数相等，并且求可能的最终序列个数。

---

解题思路

在差分数组上操作，那么操作变为将差分数组上一个数 + 1 +1 +1且一个数 − 1 -1 −1（当然当 l = 1 l=1 l=1或 r = n r=n r=n时就是只改变一个数）。所以最少操作数就是正数的和和负数的绝对值和的最大值。

序列种数，假设正数和 z z z大于负数和 f f f，那么其实对于 f ∼ z f\sim z f∼z这个范围内的我们都可以选择是让 l = 1 l=1 l=1来修改或者 r = n r=n r=n来修改，所以个数和就是 a b s ( f − z ) + 1 abs(f-z)+1 abs(f−z)+1

---

c o d e code code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll n,a[1100000],z,f;
int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		ll x=a[i]-a[i-1];
		if(i==1)continue;
		z+=(x>0)*x;f-=(x<0)*x;
	}
	printf("%lld\n%lld",max(z,f),abs(z-f)+1);
}