Straight Master Gym - 101775J （差分的应用）

思路：以前没做过差分的题目，这题想不到用差分，感觉很神奇。

思路：构造差分序列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 

上面的分析已经很透彻了，这里讲一下为什么只要保证距离不小于三就行（题目要求可以打出3,4,5张牌），其实也很好理解，我们将打牌转化成了区间减去1的问题，只要这个区间大于等于3，那么不管它是多少，都可以分解成3,4,5这样的子区间，所以只要保证不小于三就行。

下面补充点差分的性质：

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

一个序列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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=2e5+7;
const int mod=1e9+7;
ll a[maxn],sum[maxn];
int n;
bool solve()
{
    int pos=4;
    for(int i=1;i<=n+1;i++)
    {
        while(sum[i]>0)
        {
            while(pos<=n+1&&sum[pos]>=0) pos++;
            if(pos>n+1||pos-i<3) return false;
            if(sum[pos]+sum[i]>=0)
            {
                sum[i]+=sum[pos] ;
                sum[pos]=0;
            } 
            else
            {
                sum[pos]+=sum[i];
                sum[i]=0;
            }
        }
        if(sum[i]!=0) return false;
    }
    return true;
}
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int T;
    cin>>T;
    int Case=0;
    while(T--)
    {
        scanf("%d",&n);
        a[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            sum[i]=a[i]-a[i-1];
        }
        sum[n+1]=0-a[n];
        bool ans=solve();
        printf("Case #%d: ",++Case);
        if(ans)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}