J - Straight Master Gym - 101775J ----差分

题意：给你一个序列，每次可以随便选一个大小为3~5的区间，将区间内的数减1，问最后能不能把整个序列变为0

思路：构造差分序列b【i】=a【i】-a【i-1】，比如1 3 2 5 1的差分序列就是1 2 -1 3 -4，这样将区间【l，r】内的所有数减一相当于把b【l】减一， 把b【r+1】加一，基于这个思想我们从左到右扫整个序列，遇到正数就找他右面离他最近的负数，把这个负数尽量变为0，变为0后若正数还有剩余，就继续往右找负数直到这个正数用完，当然找到负数以后要判断一下负数与正数之间的距离是否小于三，小于三肯定不满足题意了，直接输出no就好了，这样扫完整个序列后差分数组的每个数应该都是0，都是0的话输出yes，否则no

差分就是将一串数分别于前一个数做差，例如：

一个序列1 2 5 4 7 3，差分后得到1 1 3 -1 3 -4 -3

这里注意得到的差分序列第一个数和原来的第一个数一样（相当于第一个数减0）

差分序列最后比原序列多一个数（相当于0减最后一个数）

性质：

1、差分序列求前缀和可得原序列

2、将原序列区间[L,R]中的元素全部+1，可以转化操作为差分序列L处+1，R+1处-1

3、按照性质2得到，每次修改原序列一个区间+1，那么每次差分序列修改处增加的和减少的相同

#include <iostream>
#include<algorithm>
#include<stack>
#include<cmath>
#include<queue>
#include<string.h>
#include<stdio.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
ll top;
int main()
{
    ll t,n,x;
    scanf("%lld",&t);
    ll s[200005];
    while(t--)
    {
        scanf("%lld",&n);
        int flot=1;
        memset(s,0,sizeof(s));
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&x);
            s[i]+=x;
            s[i+1]-=x;
        }
        int p=4;
        for(int i=1; i<=n+1; i++)
        {
            while(s[i]>0)
            {
                while(p<=n+1&&s[p]>=0)
                    p++;
                if(p>n+1||p-i<3)
                {
                    flot=0;
                    break;
                }
                if(s[i]+s[p]<=0)
                {
                    s[p]+=s[i];
                    s[i]=0;
                }
                else
                {
                    s[i]+=s[p];
                    s[p]=0;
                }
            }
            if(!flot)
                break;
        }
        if(flot)
            printf("Case #%lld: Yes\n",++top);
        else
            printf("Case #%lld: No\n",++top);
    }
    return 0;
}