2017 EC final J Straight Master（差分）

题目链接

题意

有n种扑克牌，每种扑克牌有ai张，每次可以打出3到5张连续的牌作为顺子，问这副牌能不能用顺子全打出来

思路

以前只知前缀和，区间修改跑前缀和之类的，没想过还能主动先做一次前缀和的逆运算。
先构造差分序列，原序列L，R]区间加1，等价 差分序列L处+1，R+1处-1。题目即等价于按一定规则主动构造这个差分序列。
还有一点，关于长度大于5的区间，比如连打6张牌，我们可以三张三张扔，所以构造时无需管上界


优化至O(n)，i+3如果为负，只可能在小于等于i的范围内消掉。所以i从1开始枚举，同时将i+3进行加入判断

代码

#include <stdio.h>

const int N = 2e5+5;

int v[N], d[N];

int solve(int n)
{
    int now = 0;
    for(int i = 1, j = 4; i <= n; ++i, ++j)
    {
        if(d[i] > 0) now += d[i];
        if(j <= n && d[j] < 0) now += d[j];
        if(now < 0) return 0;
    }
    return now == 0;
}

int main()
{
    int t, ca = 1, n;
    for(scanf("%d",&t); ca <= t; ++ca)
    {
        scanf("%d",&n);
        for(int i = 1; i <= n+1; ++i)
        {
            if(i != n+1) scanf("%d",&v[i]);
            else v[i] = 0;
            d[i] = v[i] - v[i-1];
        }
        printf("Case #%d: %s\n",ca,solve(n+1) ? "Yes" : "No");
    }
    return 0;
}