诡异事件

P1923 【深基9.例4】求第 k 小的数

chrispang @ 2024-05-18 17:55:23

吸引你点进来的是这个帖子的标题

p1923不是在快排分解的时候只分解其中一边的吗?可我为啥子还是60分,TLE了两个点。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, k;
vector<int> vec;
vector<int> p1923(int left, int right)
{
    if (left == right) {
        cout << vec[left] << endl;
        exit(0);
    }
    int i, j, pivot;
    i = left, j = right, pivot = vec[left];

    while (i < j)
    {
        while (vec[j] >= pivot && i < j) j--;
        while (vec[i] <= pivot && i < j) i++;

        if (i < j)
        {
            swap(vec[i], vec[j]);
        }
    }
    swap(vec[i], vec[left]);
    if (i < k) p1923(i + 1, right);
    else if(i > k) p1923(left, i - 1);
    else {
        cout << vec[i] << endl;
        exit(0);
    }
    return vec;
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        vec.push_back(t);
    }

    p1923(0, vec.size() - 1);
    return 0;
}

by kkkisbigsb @ 2024-05-21 20:50:34

我也是TLE两个点


by zhuyucheng6046 @ 2024-06-01 19:17:46

@chirspang,你要把``` cin>>t;改为scanf("%d",&t); 下一个cin也一样 正确代码:


#include<bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
scanf("%d%d",&a,&b);
    int n[a];
    for(int i=0;i<a;i++)
    scanf("%d",&n[i]);
    sort(n,n+a);
    cout<<n[b]<<endl;
    return 0;
}

by zhuyucheng6046 @ 2024-06-01 19:18:33

这个比较简单


by zhuyucheng6046 @ 2024-06-01 19:19:06

求关注!


|