Gym - 101775J Straight Master——差分

题意：给你一个序列，每次可以随便选一个大小为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

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int T, n, a[maxn], b[maxn];
bool solve() {
    int p = 4;
    for (int i = 1; i <= n+1; i++) {
        while (b[i] > 0) {
            while (p <= n+1 && b[p] >= 0) p++;
            if (p > n+1 || p - i < 3) return false;
            if (b[p] + b[i] >= 0) { b[i] += b[p]; b[p] = 0; }
            else { b[p] += b[i]; b[i] = 0; }
        }
        if (b[i] != 0) return false;
    }
    return true;
}
int main() {
    //freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    for (int ks = 1; ks <= T; ks++) {
        scanf("%d", &n);
        a[0] = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            b[i] = a[i] - a[i-1];
        }
        b[n+1] = 0 - a[n];
        printf("Case #%d: ", ks);
        if (solve()) puts("Yes");
        else puts("No");
    }
    return 0;
}