CF1442A Solution

题目链接

题解

题意可以理解为：是否能将(a)序列中的每个数分为(l_i+r_i)，并满足(l)序列单调不升，(r)序列单调不降。以(l)举例，如果想从左边减去(a_i)，一定会减去(a_i)左侧的每一个数，因此(l_i)单调不升。为满足此，(l_i)一定(le l_{i-1})，而为满足(r_ige r_{i-1})，(l_i)需要满足(l_ile a_i-r_{i-1})。在这两个限制条件下，贪心使(l_i)取最大值（最大值会给后续更大的选择空间），如果出现(l_i<0)则无法实现。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=30010;
int a[N];
int main()
{
	int t,n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		int l=a[1],r=0;
		for(int i=2;i<=n;i++)
		{
			l=min(l,a[i]-r); r=a[i]-l;
			if(l<0) {printf("NO
"); break;}
			if(i==n) printf("YES
");
		}
		if(n<=1) printf("YES
");//特判
	}
	return 0;
}