2017-2018 ACM-ICPC Asia East Continent League Final J. Straight Master(差分+思维)

LINK]

首先能每次选择长度为 3 , 4 , 5 3,4,5 3,4,5的区间长度加一

相当于可以让长度大于等于 3 3 3任意的区间整体加一,因为 3 , 4 , 5 3,4,5 3,4,5可以凑成任意数

但这样还是不好写,考虑把原数组差分为数组 a a a

那么让区间 [ l , r ] [l,r] [l,r]整体加一相当于 a l + + , a r + 1 − − a_l++,a_{r+1}-- al​++,ar+1​−−

所以若 a i > 0 a_i>0 ai​>0,说明存在 a i a_i ai​个以 i i i开头的区间

若 a i < 0 a_i<0 ai​<0,说明存在 a i a_i ai​个以 i i i结尾的区间

所以我们肯定需要让所有大于零的位置去匹配掉所有小于零的位置

并且因为不能匹配长度小于 3 3 3的区间,所以每个右端点都应该匹配掉右边离自己最近的左端点

因为如果自己不能匹配,右边的右端点就更不能匹配了

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
int n,t,a[maxn],cha[maxn],casenum;
int main()
{
	cin >> t;
	while( t-- )
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)	scanf("%d",&a[i] );
		a[++n] = 0;
		for(int i=1;i<=n;i++)	cha[i] = a[i]-a[i-1];
		long long sum = 0;
		for(int i=1;i<=n;i++)
		{
			if( cha[i]>0 )	sum += cha[i];
			if( i+3<=n && cha[i+3]<0 )	sum += cha[i+3];
			if( sum<0 )	break;
		}
		cout << "Case #" << ++casenum << ": ";
		if( cha[3]<0 || cha[2]<0 || cha[1]<0  || (sum!=0) )	cout << "No\n";
		else	cout << "Yes\n";
	}
}