Codeforces Round #681 D. Extreme Subtraction（差分+思维）

本文主要是介绍Codeforces Round #681 D. Extreme Subtraction（差分+思维），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

D.Extreme Subtraction

题目传送门：
Extreme Subtraction

题目大意：

有一个长度为n的数组a。你可以进行无数次如下操作：

a1~ai 减1
ai~an减1

问能否使数组中的元素全部变成0；

思路：

转化成一个差分问题。(假设差分数组为ans)要使数组中的全部数都为0，那么差分数组也必须为0且ans[1]=0。
那么我们来看两种操作对于差分数组有何影响：

操作1：ans[1]-1 且ans[i+1]+1。那么我们就可以凭借操作1，将差分数组中的负数变成0，同时减小ans[1]。

操作2：ans[i+1]-1且ans[n+1]+1。那么我们就可以凭借操作2，将差分数组中的正数变成0，而ans[n+1]为多少和我们并没有关系。

在最开始时ans[1]=a[1]，所以只要差分数组的负数和的绝对值小于等于a[1],即输出YES，否则输出NO。
因为如果差分数组的负数和的绝对值大于a[1],那么要使后面的数都变成0，ans[1]就会变成负数，而并没有使ans[1]由负数变成0的操作，操作2只能使ans[1]由正数变成0，所以这样并不满足要求。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
int a[N];
int ans[N];
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);a[0]=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);ans[i]=a[i]-a[i-1];}int res=0;for(int i=2;i<=n;i++)if(ans[i]<0) res=res+(-1)*ans[i];if(res<=a[1]) printf("YES\n");else printf("NO\n");}//system("pause");return 0;
}