c576: 不快速的快速排序
標籤 :
通過比率 : 34% (10 人 / 29 人 ) (非即時)
評分方式:
Special

最近更新 : 2018-05-06 18:24

內容

快速排序法的平均時間複雜度是 $O(n \log n)$,然而在某些情況下可能轉為糟糕的$O(n^2)$。
例如總是選擇一端的元素當作 pivot ,複雜度在已排序的序列上就會因為每次只選到最大值或最小值而退化。


當然,我們可以透過加入隨機成分來解決這個問題,但事情往往不如預期地單純。
現在給你一份程式碼,請你構造一組合法的輸入,使得排序無法在一秒內完成。

#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;
}
輸入說明

本題沒有輸入。

輸出說明

首行輸出一個整數$\space 1 \leq N \leq 30000\space$,代表你的序列長度。

第二行輸出$\space N \space$個相異$\space 32 \space$位元有號整數,中間以空格隔開。

如果你的輸出格式有誤或是沒達到要求,會得到一個 WA。

以下為一組合法但不會 AC 的輸出。

範例輸入

										
範例輸出
5
1 2 3 4 5
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.5s , <1K
提示 :

如果在 seed 改變的時間附近上傳,可能會拿到 RE (code: 111)。

請注意,直接輸出順序或逆序的數列基本上是無法通過測試的,因為 rand() 會破壞這個性質。

標籤:
出處:
[編輯:
icube (我都不會)
]


編號 身分 題目 主題 人氣 發表日期
14212
icube (我都不會)
c576
43 2018-06-28 20:47