头像

Udsnf


访客:58

离线:6小时前



Udsnf
8天前

题目链接 AcWing 785

已经随机化处理 但还是超时 leetcode 是可以通过的

错误的代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, a[N];

int part(int L, int R) {
    int p = rand() % (R - L + 1) + L;// p = (L + R) / 2 也超时
    swap(a[p], a[R]);
    int i = L;
    for (int j = L; j < R; ++j) {
        if (a[j] < a[R]) swap(a[i++], a[j]);
    }
    swap(a[i], a[R]);
    return i;
}

void qs(int L, int R) {
    if (L >= R) return;
    int p = part(L, R);
    qs(L, p - 1);
    qs(p + 1, R);
}

int main() 
{
    cin >> n; 
    for (int i = 0; i < n; ++i) cin >> a[i];
    qs(0, n - 1);
    for (int i = 0; i < n; ++i) cout << a[i] << " ";
    return 0;
}

TLE