Straight Master （贪心）

题目如下：
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?

he 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.
.

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.

题目大意就是给好多堆纸牌我们一次可以在相邻的三堆各取一张纸牌或者相邻的四堆中各取一张纸牌或者五堆中各取一张纸牌问能不能全部取完

数据量也比较大贪心简单做

在做这个题目前要先搞懂一件事情就是3 4 5可以拼成任何大于三的数字比如 7=4+3 9=3+3+3

贪心策略赶紧并不是很好想

可以先举例子

我在这里放了11堆的例子这11堆安照题目中的规则是可以取完的

为了证明他是可以取完的我做了下面这串表在下面中的每一行中都有数目不少于3个的相同数字
刚才也说过 3 4 5可以组合成任何不小于3的数字也就是下面的每一行的个数我都可以用3 4 5获得

1	2	3	3	5	8	10	5	6	7	4	2
1	1	1	1	1	1	1
	1	1	1	1	1	1
		1	1	1	1	1
				2	2	2
					3	3	3	3	3
						2	2	2	2	2
								1	1	1	1
									1	1	1

我将上面堆数字做下处理如下相邻的相同颜色的几堆代表这被取走的几堆数值代表取多少次

1	2	3	3	5	8	10	5	6	7	4	2
1	1	1	1	1	1	1
	1	1	1	1	1	1
		1	1	1	1	1
				2	2	2
					3	3	3	3	3
						2	2	2	2	2
								1	1	1	1
									1	1	1

通过简单的观察和逻辑推理就可以注意到如果我们第 i 堆比第 i-1 堆要大的话那么大出来的那部分一定是某次取牌的最左端的位置
如果第 i 堆比第 i-1 堆小就不能确定了但是呢第 i 堆要满足一个条件就是不能断了前两堆产生的新最左端位置意思就是第i堆的数目一定要不小于前三堆正差的和否则会产生一个断层就无解了在这一堆的结束位置也要满足一个条件就是倒数第二堆不能产生新的左端点如果产生就要n+1给补上显然是不可以的还有就是倒数第三堆产生的左端点一定要由末尾补上否则也是无解

#include<iostream>

#include<stdio.h>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn = 2e5+;

int a[maxn],b[maxn],flag;

int main()

{

int T,n,cases=;

scanf("%d",&T);

while(T--){

scanf("%d",&n);

n++;

flag=;

for(int i=;i<=n;i++){

scanf("%d",a+i);

b[i]=max(a[i]-a[i-],);

}

if(n<=){

printf("Case #%d: No\n",++cases);

continue;

}

   for(int i=;i<=n;i++){

if(a[i]<b[i-]+b[i-])

flag=;

}

if(!(b[n]==&&b[n-]==&&a[n]>=b[n-]))

{

   flag=;

}

if(!flag)

    printf("Case #%d: Yes\n",++cases);

else

    printf("Case #%d: No\n",++cases);

}

return ;

}

巴特西

Straight Master （贪心）

最新文章

热门文章