IncDec Sequence （差分）

题目地址

这道题可以用来检测一下你是否学会了差分，或者你可以更加透彻的理解差分

我们把 \(cf[]\) (差分)数组拿出了，就可以发现这道题就是每次可以在 \(cf[]\)中选两个数，一个+1，一个-1，如何用最少的步数吧 \(cf[2]-cf[n]\) 中的所有数变成0

考虑到 \(cf[]\) 数组中有负数也有正数，我们设 \(p\) 是所以负数之和，\(q\) 是所以正数之和，我们肯定优先正负抵消，设正负抵消后还有 \(|p-q|\)，这是我们让它和 \(cf[1]\) 或者 \(cf[n+1]\) 消，所以最短步数是 \(\text{max}(p,q)\)，不同最后值是 \(|p-q|+1\)

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5+7;

int n,p,q;

int a[N],cf[N];

signed main()

{

	scanf("%lld",&n);

	for(int i=1;i<=n;++i) {

		scanf("%lld",&a[i]);

		cf[i] = a[i] - a[i-1];

	}

	for(int i=2;i<=n;++i) {

		if(cf[i] > 0) p += cf[i];

		if(cf[i] < 0) q += -cf[i];

	}

	printf("%lld\n%lld\n",max(p,q),abs(p-q)+1);

	return 0;

}

巴特西

IncDec Sequence （差分）

题目地址

最新文章

热门文章