接龍啊…
小測資照著題目做就可以過,但大測資不行,必須優化,可以優化成 O(n)
。
該如何優化呢?為了解釋,我們先簡化問題,不考慮花色,於是題目變成:
一連續正整數序列,打亂後,求最少須要「遍歷序列」幾次才可以整理好所有數字 。
例如:
4 1 8 2 5 6 3 7 9
需要三次遍歷,分別為:
1 2 3
4 5 6 7
8 9
根據題意,一次遍歷挑出來的這些數字一定會是連續的,所以可以有這個想法:
從左到右處理每一項,當在處理
a[i]
時,如果a[i]-1
已經出現過了,那麼a[i]
必會在a[i]-1
被挑出去的那次遍歷裡被挑出去。
這可以用 開一個大陣列,記錄各個值有沒有出現過 的方法來得到 O(1) 的時間複雜度,也就是說,用空間換取時間。
再來我們得找出每次遍歷的第一個數字是誰。 跟前述同樣的想法:
在處理
a[i]
時,如果a[i] - 1
還沒出現過,那麼它就是這次遍歷的第一個值。
因為每次遍歷的第一個數字,必為上次遍歷挑出來的那些數字中,最大的那個數字再加一。
如果要整理好 a[i]
,則必需要增加一次遍歷,才會/能把 a[i]
挑出來。
綜合上述兩個論述,及第一次遍歷第一個數字必為 1
的事實,想得知最少要遍歷幾次,可以寫成以下式子:
int cnt = 0;
bool ob[MAX_VALUE]; // occurred before, each item default false
for (int& x : data) {
ob[x] = true;
if (x == 1)
cnt++;
else if (ob[x-1])
continue;
else
cnt++;
}
我們再考慮原題目,可以發現顏色之間互不影響,所以可以直接改寫,最後的結果就是各顏色所需最少遍歷次數的最大值,程式碼請參文末。
naive:
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<char, int> P;
int main() {
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
int N;
cin >> N;
vector<P> data(N);
for (int i = 0; i < 4 * N; i++) {
string inp;
cin >> inp;
int rank = stoi(inp.substr(1, inp.length() - 1));
char color = inp[0];
data.push_back(P(color, rank));
}
int s_slot = 0;
int h_slot = 0;
int d_slot = 0;
int c_slot = 0;
int cnt = 0;
while (s_slot + h_slot + d_slot + c_slot != 4*N) {
vector<P> discard;
for (P& card : data) {
int rank = card.second;
char color = card.first;
if (color == 'S' && s_slot == rank - 1)
s_slot++;
else if (color == 'H' && h_slot == rank - 1)
h_slot++;
else if (color == 'D' && d_slot == rank - 1)
d_slot++;
else if (color == 'C' && c_slot == rank - 1)
c_slot++;
else
discard.push_back(card);
}
cnt++;
data = discard;
}
cout << cnt << "\n";
}
return 0;
}
AC Code
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
bool ob[4][150000+1];
int cnt[4];
int main() {
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
int N;
cin >> N;
memset(ob, false, sizeof(ob));
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < 4 * N; i++) {
string inp;
cin >> inp;
const static string colors = "SHDC";
int color = colors.find(inp[0]);
int rank = stoi(inp.substr(1, inp.length() - 1));
ob[color][rank] = true;
if (rank == 1)
cnt[color]++;
else if (ob[color][rank-1])
continue;
else
cnt[color]++;
}
cout << *max_element(cnt, cnt+4) << "\n";
}
return 0;
}