题目来源 Straight Master
题意
有n种扑克牌，每种扑克牌有ai张，每次可以打出3到5张连续的牌作为顺子，问这副牌能不能用顺子全打出来
思路
换一个思路，给定一个长度为0的序列，每次可以选择长度为3,4,5的区间并将这个区间内的数全部加一，最终可以得到一个新的序列，问这个序列的每个数分别是多少，这个序列就是给定的n种扑克牌。
对于这个问题，可以用差分的思想，对于区间[L, R]，可以开一个新的数组b，这个区间加一后可以认为是b[L]+=1, b[R+1]-=1, b的前缀和即为对应的数字。
原来那个问题就可以转化为给你一个序列，问这个序列可不可以由上面的操作得到。也可以构建一个差分数组b，其中b[i] = a[i]-a[i-1]。如果这个b数组对于每个相邻距离大于等于3的b[i] 和 b[j] (j>=i+3)，如果每一对的和加起来等于0，则给定的数列是可以得到的，否则就无法得到。
代码
#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了好几发，然后判断前缀和满不满足条件的时候写到了花括号里。。。智障。。。
