題目連結：
題目大意：
給定以下實作快速排序法（Quick Sort）的程式碼：
#include <bits/stdc++.h>
using namespace std;
int N, a[30010];
void Init() {
unsigned int seed = time(0) / 60;
srand(seed);
}
struct cmp {
int x;
cmp(int x): x(x) {
}
inline bool operator()(int y) {
return y < x;
}
};
void quicksort(int l, int r) {
if (r - l <= 1) return;
swap(a[l], a[l + rand() % (r - l)]);
int pivot = stable_partition(a + l + 1, a + r, cmp(a[l])) - a;
swap(a[l], a[pivot - 1]);
quicksort(l, pivot - 1), quicksort(pivot, r);
}
int main() {
Init();
cin >> N;
for (int i = 0; i < N; ++i) cin >> a[i];
quicksort(0, N);
for (int i = 0; i < N; ++i) cout << a[i] << ' ';
return 0;
}
由於快速排序法最佳時間複雜度為 Ｏ（ＮlogＮ） ，但是也有可能退化為 Ｏ（Ｎ ^ ２）。雖然加入「隨機」的元素可以盡量避免此問題。但是精心設計的數列還是有可能使其退化。
而這題的目標即是生成這樣子的一個數列，使得以上的排序程式碼無法在 １ 秒之內完成。
第一列要輸出一正整數 Ｎ （１ ≦ Ｎ ≦ ３０, ０００），代表接下來要輸出的序列長度。接著的一列即是數列的內容。見範例輸出。其中，數列中的數字必須為相異的３２位元有號整數。
範例輸入：
此題無輸入。
範例輸出：
以下為一組合法（符合格式），但不會讓程式超時的範例：
5
1 2 3 4 5
解題思維：
本次討論著重於 C 與 C++ 的 rand() 函式之實作方法。想參考 Python 的 rand() 函式實作，請見本題作者的討論。另外，也不討論快速排序的演算法，欲知詳情請參照 wiki 或是這則影片等等。
先來分析題目的程式碼：
我們可以看到快速排序的部分，在挑選一開始的基準點（或稱「樞紐」，即為 Pivot ）的時候，是使用 rand() 函式去取索引值（Index）介於 l ～ r （含 l ，但不含 r）的數字。
將其跟最左邊的數字交換，並使用 stable_partition() 函式以此區分左右半邊（比基準點小的在左邊，剩下的在右邊）。然後，將最左邊的基準點跟分界點（區分左右半邊的點）交換。之後，使用遞迴去排序左右半邊。
再來是 rand() 的部分，其使用了 time(0) / 60 作為產生隨機序列的種子（Seed），而只要種子一樣生成的序列是一樣的。
因為 C++ 的 rand() 之實作類似於，有一函式 Ｆ（ｘ） 。一開始將種子代入 Ｆ ，求得序列的第一個數字 ｎ１ ；接著，將 ｎ１ 代入 Ｆ ，求得序列的第二個數字 ｎ２ …… 以此類推。所以種子一樣，生成的序列當然就一樣。
而這邊使用 time(0) / 60 作為種子，也就是現在於過去的某個時間點經過的秒數除以 ６０ ，關於 time() 之詳細請見這裡。只要我們使用一樣的種子，也就是 time(0) / 60 ，我們就可以生成一樣的序列。
而快速排序的部分使用到了 rand() 作為取基準點的方法。因此我們就可以預先知道程式會取那些數字作為基準點，進而可以去生成一個特殊的序列，達成題目的要求。
那要怎麼生成一個這樣子的序列呢？假設排序為由小到大，而且每次的左右半邊皆為「沒有左邊，只有右邊」，意即每次挑到的數字都是當前未排序的數字中最小的。並假設 rand() 生成了以下長度為 ９ 的序列：
5 13 6 6 7 9 8 4 1
而我們要排序的序列長度為 １０ 。
（以下的索引值從 ０ 開始）
5 13 6 6 7 9 8 4 1
首先，基準點要挑目前所剩數字的第 ５ ％ １０ ＝ ５ 個，而我們想讓現在挑到的數字為目前未排序的數字中最小的一個，假設為 ０ 。則數字 ０ 應該要排在原本序列的第 ５ 個位置：
＿、＿、＿、＿、＿、０、＿、＿、＿、＿
5 13 6 6 7 9 8 4 1
再來，基準點要挑目前所剩數字的第 １３ ％ ９ ＝ ４ 個。假設目前最小數字為 １ 。則數字 １應該要排在原本序列的第 ４ ＋ １ 個位置（＋ １ 是因為進行一次左右邊的分割後，前面會有一個數字留下，即為數字 ０）。
但是因為原本的第 ５ 號位置已經被 ０ 佔走了。而我們知道數字 ０ 經過一次交換後，會跑到最左邊的位置，因此：
１、＿、＿、＿、＿、０、＿、＿、＿、＿
5 13 6 6 7 9 8 4 1
再來，基準點要挑目前所剩數字的第 ６ ％ ８ ＝ ６ 個。假設目前最小數字為 ２ 。則數字 ２ 應該要排在原本序列的第 ６ ＋ ２ 個位置：
１、＿、＿、＿、＿、０、＿、＿、２、＿
5 13 6 6 7 9 8 4 1
再來，基準點要挑目前所剩數字的第 ６ ％ ７ ＝ ６ 個，假設目前最小數字為 ３ 。則數字 ３ 應該要排在原本序列的第 ６ ＋ ３ 個位置：
１、＿、＿、＿、＿、０、＿、＿、２、３
5 13 6 6 7 9 8 4 1
再來，基準點要挑目前所剩數字的第 ７ ％ ６ ＝ １ 個，假設目前最小數字為 ４ 。則數字 ４ 應該要排在原本序列的第 １ ＋ ４ 個位置。
但是因為第 ５ 個位置已經被 ０ 佔走，所以試圖放 ０ 預計會到的最左邊。但是也不行，因此再試試數字 １ 會到的地方，也就是第 １ 個位置。這樣子數字 ０ 、 １ 分別到最左邊後，數字 ４ 就會在現在要取的第 ５ 個位置：
１、４、＿、＿、＿、０、＿、＿、２、３
5 13 6 6 7 9 8 4 1
再來，基準點要挑目前所剩數字的第 ９ ％ ５ ＝ ４ 個，假設目前最小數字為 ５ 。則數字 ５ 應該要排在原本序列的第 ４ ＋ ５ 個位置。
同理，此位置已經被佔掉了，因此試圖放在數字 ４ 最終會到的地方，即第 ３ 個位置：
１、４、＿、５、＿、０、＿、＿、２、３
5 13 6 6 7 9 8 4 1
再來，基準點要挑目前所剩數字的第 ８ ％ ４ ＝ ０ 個，假設目前最小數字為 ６ 。則數字 ６ 應該要排在原本序列的第 ０ ＋ ６ 個位置：
１、４、＿、５、＿、０、６、＿、２、３
5 13 6 6 7 9 8 4 1
再來，基準點要挑目前所剩數字的第 ４ ％ ３ ＝ １ 個，假設目前最小數字為 ７ 。則數字 ７ 應該要排在原本序列的第 １ ＋ ７ 個位置。
同理，已經被佔掉了，所以放去第 ２ 個位置：
１、４、７、５、＿、０、６、＿、２、３
5 13 6 6 7 9 8 4 1
再來，基準點要挑目前所剩數字的第 １ ％ ２ ＝ １ 個，假設目前最小數字為 ８ 。則數字 ８ 應該要排在原本序列的第 １ ＋ ８ 個位置。
同理，第 ９ 、 ３ 、 ５ 、 ０ 、 １ 都被佔掉了，因此最後放到第 ４ 個位置：
１、４、７、５、８、０、６、＿、２、３
最後，剩下一個要放的數字，假設為 ９ 。因此我們就得到了會讓快速排序每次都會挑到最小的數字、長度為 １０ 之序列（前提是 rand() 生成的序列為 5 13 6 6 7 9 8 4 1）：
１、４、７、５、８、０、６、９、２、３
而把以上的生成方式套用到長度 ３０, ０００ 的序列也可以發揮作用。於是，生成數列後將數列照著輸出格式輸出即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
