EC-final2017 J - Straight Master Gym - 101775J（差分，贪心）

A straight is a poker hand containing five cards of sequential rank, not necessarily to be the same suit. For example, a hand containing 7 club, 6 spade, 5 spade, 4 heart and 3 diamond forms a straight. In this problem, we extend the definition of a straight to allow 3 to 5 cards of sequential rank. Hence a hand containing K spade, Q club, and J heart is also a straight.

Mr. Panda is playing a poker game called Straight Master. The game uses a large deck of card that has N ranks from 1 to N. The rule of the game is simple: split the cards in Mr. Panda’s hand into several straights of length from 3 to 5.

Now given a hand of cards, can you help Mr. Panda to determine if it is possible to split the cards into straights?

Input
The first line of the input gives the number of test cases, T. T test cases follow.

Each test case contains two lines. The first line contains an integer N, indicating the number of ranks in the deck. The next line contains N integers a1, a2, …, aN indicating the number of cards for each rank in Mr. Panda’s hand.

1 ≤ T ≤ 100.
1 ≤ N ≤ 2 × 105.
0 ≤ ai ≤ 109.
.
Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is Yes if Mr. Panda can split all his cards into straights of length from 3 to 5, or No otherwise.

Example
Input
2
13
1 2 2 1 0 0 0 0 0 0 0 0 0
13
1 1 1 1 0 1 1 0 0 0 0 0 0
Output
Case #1: Yes
Case #2: No
Note
In the first test case, Mr. Panda can split his cards into two straights: [1, 2, 3] and [2, 3, 4]. In the second test case, there is no way to form a straight for card 6 and 7.

题意： 每次可以选连续的3到5个数字，去掉。给出一堆数字，问能不能把所有的数字去掉
思路：
看到3-5想到了dp。但是状态咋记录？？正着和反着都有后效性。
没想到没想到，这是个数学题——3，4，5可以组成1，2外的所有正数
（这里可以用裴蜀定理证明，因为3,4,5的gcd是1，那么可以有3x + 4y + 5z = d，只要d > 5，就保证x,y,z ≥ 0。同时这种证明能否表示所有数的，一般可以用数学归纳。其他想法也有比如 x%3 = 0的话，x = 3k。x%3 = 1,x = 3k + 4。x % 3 = 2，x = 3k + 5.）
于是每次选大于3的段整段整段的去掉。如果最后全部去掉了，就说明是对的。区间段的修改用差分维护，对于差分有了更深的理解。

维护b[i] = a[i] - a[i - 1].
比如 2 2 2 1 1 1，b[1] = 2,b[4] = -1.那么第一次去掉，变成了1 1 1 1 1 1，b[1]变成了1，b[4]变成了0
而1 1 1 2 2 2. b[1] = 1,b[7] = -2.第一次去掉0 0 0 1 1 1, 此时b[1]变成了0，b[7]变成了1。通过差分数组的单点修改实现了区间修改的功能。

#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
#include<queue>
#include<string.h>
#include<stdio.h>

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 7;

ll a[maxn],b[maxn];

int main()
{
    int T;scanf("%d",&T);
    int kase = 0;
    while(T--)
    {
        int n;scanf("%d",&n);
        memset(b,0,sizeof(b));
        memset(a,0,sizeof(a));
        for(int i = 1;i <= n;i++)
        {
            scanf("%lld",&a[i]);
        }
        for(int i = 1;i <= n + 1;i++)
        {
            b[i] = a[i] - a[i - 1];
        }
        
        int r = 4,flag = 0;
        for(int l = 1;l <= n + 1;l++)
        {
            
            while(b[l] > 0)
            {
                while(r <= n + 1 && b[r] >= 0)r++;
                if(r > n + 1 || r - l < 3)
                {
                    flag = 1;
                    break;
                }
                if(b[r] + b[l] >= 0)
                {
                    b[l] += b[r];
                    b[r] = 0;
                }
                else
                {
                    b[r] += b[l];
                    b[l] = 0;
                }
            }
            if(flag)break;
        }

        if(flag == 1)
            printf("Case #%d: No\n",++kase);
        else
            printf("Case #%d: Yes\n",++kase);
    }
    return 0;
}