題目來源 Straight Master

題意

有n種撲克牌，每種撲克牌有ai張，每次可以打出3到5張連續(xù)的牌作為順子，問這副牌能不能用順子全打出來

思路

換一個思路，給定一個長度為0的序列，每次可以選擇長度為3,4,5的區(qū)間并將這個區(qū)間內(nèi)的數(shù)全部加一，最終可以得到一個新的序列，問這個序列的每個數(shù)分別是多少，這個序列就是給定的n種撲克牌。

對于這個問題，可以用差分的思想，對于區(qū)間[L, R]，可以開一個新的數(shù)組b，這個區(qū)間加一后可以認(rèn)為是b[L]+=1, b[R+1]-=1, b的前綴和即為對應(yīng)的數(shù)字。

原來那個問題就可以轉(zhuǎn)化為給你一個序列，問這個序列可不可以由上面的操作得到。也可以構(gòu)建一個差分?jǐn)?shù)組b，其中b[i] = a[i]-a[i-1]。如果這個b數(shù)組對于每個相鄰距離大于等于3的b[i] 和 b[j] (j>=i+3)，如果每一對的和加起來等于0，則給定的數(shù)列是可以得到的，否則就無法得到。

代碼

#include <bits/stdc++.h>
using namespace std;
int n, a[200005], b[200005];
int main()
{
    int t;
    scanf("%d", &t);
    for (int cas = 1; cas <= t; ++cas)
    {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));

        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", a + i);

        b[0] = a[0];
        for (int i = 1; i < n; ++i) b[i] = a[i] - a[i - 1];
        b[n] = -a[n - 1];

        bool ok = true;
        if (b[0] < 0 || b[1] < 0 || b[2] < 0)   ok = false;
        else
        {
            long long sum = 0;
            for (int i = 0; i <= n; ++i)
            {
                if (b[i] > 0)   sum += b[i];
                int p = i + 3;
                if (p > n)  break;
                if (b[p] < 0)
                {
                    sum += b[p];
                    b[p] = 0;
                }
                if (sum < 0)    break;
            }
            if (sum != 0)   ok = false;
        }
        printf("Case #%d: %s\n", cas, ok ? "Yes" : "No");
    }
    return 0;
}

這個題真的是。。。輸出格式弄錯了wa了好幾發(fā)，然后判斷前綴和滿不滿足條件的時候?qū)懙搅嘶ɡㄌ柪?。。。智障。。?/p>