Gym - 101775J(2017 EC final) - 差分序列

题目链接:点击这里

 

解题思路:

差分序列:b[i] = a[i] - a[i-1]

原序列为: 1 4 5 8 7 差分后: 1 3 1 3 -1 -7,多出来的以为可以看做0 - a[n].

差分序列的性质:前i项和等于原序列的a[i],这个很容易就能证明

如果要对一个区间的数都加上1,那么就是a[l]++,a[r+1]--,之后求一下前缀和就是当前位置更新后的值了.

那不是和差分序列的性质一样吗?

对于本题来说任意大于3的长度都能分解为若干个3-5的段,那么在差分序列中值是负的说明他执行了更多的a[r+1]--，反之正的亦然.

对于负的考虑之前有没有那么的更新此时使得i这位置可以变成该负值,如果不能就是No

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mx = 2e5 + 10;
int n,m,a[mx],b[mx];
int main()
{
	int t,ca = 1;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=0;i<n;i++) scanf("%d",a+i);
		b[0] = a[0];
		a[n] = 0;
		for(int i=1;i<=n;i++) b[i] = a[i] - a[i-1];
		int flag = 1;
		if(b[1]<0||b[2]<0) flag = 0;
		else{
			ll sum = 0;
			for(int i=0;i<=n;i++){
				if(b[i]>0) sum += b[i];
				int p = i + 3;//大于三的长度可以任意分解成若干个3-5的段 
				if(p>n) break;
				if(b[p]<0) sum += b[p];
				if(sum<0) break;//如果是负的,说明b[p]没有被清除掉,之后也不会被清除掉,所以No 
			}
			if(sum) flag = 0;
		} 
		printf("Case #%d: %s\n",ca++,flag?"Yes":"No");
	}
	return 0;
}