1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <vector>
using namespace std;
#define MIN_SHUNZI_LEN 5
#define MAX_CARD_NUM 13
#define SMALL_KING_CARD_NUM 52
#define BIG_KING_CARD_NUM 53
/*
*find the max length of shunzi
*/
int findMaxLenOfShunZi(int* cardArr, int cardCount){
//检查参数
if(cardCount < MIN_SHUNZI_LEN ){
return 0;
}
//用来记录连续区域与区域长度, +2用来加上左右两个端点，方便后续计算
vector<int> szLenVec(MAX_CARD_NUM+2, 0);
//记录大小王牌的个数
int kingCardCount = 0;
//依次放入牌，更新连续区域的长度
for(int i = 0; i < cardCount; ++i){
//如果是大小王牌则不做处理，记录大小王牌的张数
if(cardArr[i] == SMALL_KING_CARD_NUM || cardArr[i] == BIG_KING_CARD_NUM){
kingCardCount++;
continue;
}
//获取牌的点数;cardNum >= 1 && <= MAX_CARD_NUM
int cardNum = cardArr[i] % MAX_CARD_NUM + 1;
//如果是重复的牌，则不做处理
if(szLenVec[cardNum] != 0){
continue;
}
//计算放入这张牌后，所连结的左右区域的总长度
szLenVec[cardNum] = 1 + szLenVec[cardNum-1] + szLenVec[cardNum+1];
//更新该区域左端点的区域长度
int endPoint = cardNum - szLenVec[cardNum-1];
szLenVec[endPoint] = szLenVec[cardNum];
//更新该区域右端点点区域长度
endPoint = cardNum + szLenVec[cardNum+1];
szLenVec[endPoint] = szLenVec[cardNum];
}
//test
// cout << kingCardCount << endl;
// for(int i = 1; i <= MAX_CARD_NUM; ++i){
//
cout << i+1 << ": " <<
szLenVec[i] << endl;
// }
int maxShunZiLen = 0;
int shunZiLen = 0;
int startIndex = 0;
vector<int> kingIndexVec;
//放入大小王牌
int i = 0;
while(i <= MAX_CARD_NUM){
//作为一个连续区域的左端点
if(szLenVec[i] != 0){
i += szLenVec[i];
continue;
}
//....empty slot
//如果王牌没有用尽， ＋1是用来记录开始端点
if(kingIndexVec.size() < kingCardCount + 1){
//放入连续区域的左端点，用来记录放入点右边的长度
kingIndexVec.push_back(i+1);
//顺子长度加上右边连结区域的长度
shunZiLen += szLenVec[i+1];
// cout << "add shunZiLen: " << szLenVec[i+1] << " " << shunZiLen << endl;
maxShunZiLen = shunZiLen;
}else{ //如果王牌用尽，开始挪动第一个放入点到现在放入点
//move the first slot to the now slot and update the sunZiLen

//顺子长度－第一个放入点右边的长度＋现在放入点连结点右边的长度

shunZiLen += szLenVec[i+1] - szLenVec[kingIndexVec[startIndex]];
// cout << "move slot " << kingIndexVec[startIndex]-1 << 
//
" to " << i << " shunziLen: " << shunZiLen << endl;
//记录最大顺子长度
if(shunZiLen > maxShunZiLen){
maxShunZiLen = shunZiLen;
}
//保存放入点的位置
kingIndexVec[startIndex] = i+1;
//更新第一个放入点的序号
startIndex = ++startIndex % (kingCardCount + 1);
}
//进入下一个放入点
++i;
}
//加上所放入的王牌个数
maxShunZiLen += kingIndexVec.size() - 1;
return maxShunZiLen < MIN_SHUNZI_LEN ? 0 : maxShunZiLen;
}
int main(){
int n = 0;
cin >> n;
int* a = new int[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
cout << "MaxShunZiCount: " << findMaxLenOfShunZi(a, n) << endl;
}