Gym 101775J Straight Master（差分数组）

题意：
给你n个高度，再给你1_{n每种高度的数量，已知高度连续的3}5个能消去，问你所给的情况能否全部消去；例：n = 4，给出序列1 2 2 1表示高度1的1个，高度2的2个，高度3的2个，高度4的1个。那么我打出1 1 1（高度1 2 3），1 1 1（高度2 3 4）刚好打完。

思路

首先将数组进行差分获得差分数组diff（diff[i]=a[i]-a[i-1]）。
diff[i]为+ ++就相当于以 i 为起点的区间有diff[i]个。diff[i]为− -−就相当于以 i 为终点的区间有diff[i]个。
对于区间长度如何控制呢？可以发现使用3，4，5三个数字可以组成[ 3 ， ∞ ) [3，\infty)[3，∞)，所以对于区间起点可以与＞3的终点去任意组合。如果起点和终点能够完全对应上，那么就是YES，否则就是NO。
注意：差分数组开始应该有a[1]-0，最后应该有0-a[n]。还有就是如果差分数组中前两个为负数，那么就是NO。

————————————————
版权声明：本文为CSDN博主「张松超」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/ZscDst/article/details/85253125

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N =2e5 + 5;
const int M=1000000007;
int n,m,k;
int TT=1;
int a[N];
int ca[N];
void slove()
{
    cin>>n;
    int flag=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    a[++n] = 0;
    for(int i=1;i<=n;i++)
        ca[i]=a[i]-a[i-1];
    int sum=0;
    for(int i=1;i<=n;i++){
        if(ca[i]>0)  sum+=ca[i];
        if(ca[i+3]<0 && i+3<=n) sum+=ca[i+3];
        if(sum<0) break;
    }
    // cout<<sum<<endl;
    if(ca[1]<0||ca[2]<0) sum=-1;
     string ans;
     if(sum==0) ans="Yes";
     else ans="No";

    cout<<"Case #"<<TT++<<": " << ans<<endl;

}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        slove();
    return 0;
}