題干：

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,?...,?aNindicating 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?6and?7.

題目大意：

給定一個(gè)長(zhǎng)度為n的數(shù)列，初始時(shí)數(shù)列內(nèi)數(shù)字都為0。

有一個(gè)操作，可以將數(shù)列中連續(xù)的長(zhǎng)度為3、4或5的子數(shù)列中的數(shù)字全部+1。

問(wèn)多次操作后能不能將數(shù)列變成輸入的數(shù)列。
輸入第一行包含一個(gè)正整數(shù)T(1<=T<=100)，表示樣例組數(shù)。

接下來(lái)2T行，其中第i行一個(gè)數(shù)字N(1<=N<=2*10^5)表示數(shù)列長(zhǎng)度，第i+1行N個(gè)數(shù)字(0<=a<=10^9)表示最終要變成的數(shù)列；
所有N的和不超過(guò)4e6.

解題報(bào)告：

這題有一個(gè)巧妙的地方，也就是，如果你可以將連續(xù)長(zhǎng)度為3,4,5的子數(shù)列的數(shù)字都+1，那么這就等價(jià)于你可以將任意長(zhǎng)度>=3的所有子數(shù)列都+1。

所以我們可以求出差分?jǐn)?shù)組，然后枚舉每一個(gè)>0的數(shù)字，然后將它變?yōu)?，代價(jià)就是將后面從3個(gè)字符開(kāi)始，找到最近的負(fù)數(shù)，都+上對(duì)應(yīng)的一個(gè)數(shù)使之變成0.這樣操作一遍然后check數(shù)組中是否有負(fù)數(shù)，如果有的話那就GG，否則就是Yes。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int a[MAX],d[MAX],n; int main() {int t,iCase=0;cin>>t;while(t--) {scanf("%d",&n);for(int i = 1; i<=n; i++) scanf("%d",a+i);a[n+1]=0;for(int i = 1; i<=n+1; i++) d[i] = a[i] - a[i-1];int cur = 4,flag = 1;for(int i = 1; i<=n-2; i++) {if(d[i] <= 0) continue; cur = max(cur,i+3);while(d[cur] >= 0 && cur <= n+1) cur++;while(cur <= n+1 && d[i] > 0) {while(d[cur] >= 0 && cur <= n+1) cur++;if(cur > n+1) break;int dc = min(d[i],-d[cur]);//absd[i] -= dc;d[cur] += dc;}if(d[i] > 0) {flag = 0;break;}//這句加不加都可以 想想為什么}for(int i = 1; i<=n+1; i++) {if(d[i] < 0) flag = 0;}if(flag == 1) printf("Case #%d: Yes\n",++iCase);else printf("Case #%d: No\n",++iCase);}return 0 ; }

對(duì)于上面代碼中的那個(gè)疑惑，其實(shí)不難想出，因?yàn)槲覀円呀?jīng)假設(shè)，這個(gè)序列是左邊+1右邊-1這樣操作最后得到的這樣一個(gè)序列，所以我們不難發(fā)現(xiàn)+1的數(shù)量和-1的數(shù)量應(yīng)該是相同的，所以不會(huì)出現(xiàn)+1的數(shù)量過(guò)多，導(dǎo)致后面沒(méi)有-1可以供選擇這樣的情況發(fā)生。

總結(jié)

以上是生活随笔為你收集整理的【Gym - 101775J】Straight Master（差分，思维）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。