用了快排,最后两例TLE,怎么改进,求大神指点
查看原帖
用了快排,最后两例TLE,怎么改进,求大神指点
474401
qwe1471900575楼主2021/3/3 20:54
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
int a[5000050];
void work(int a[], int l, int r, int u)
{
    if (l == r)
    {
        return;
    }
    int i = l, j = r, t, k = a[(l + r) / 2];
    do
    {
        while (a[i] < k)i++;
        while (a[j] > k)j--;
        if (i <= j)
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
        }
    } while (i <= j);
    if (j >= u)work(a, l, j, u);
    else if (i <= u)work(a, i, r, u);
    else work(a, j + 1, i - 1, u);
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int l = 0, r = n - 1, u = m;
    work(a, l, r, u);
    cout << a[m];
    return 0;
}
2021/3/3 20:54
加载中...