40分求助

soyoungsolong @ 2022-07-12 11:47:52

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    int a[5000001];
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    cout<<a[k];
    return 0;
}

by Enthon_Yuan @ 2022-07-12 11:49:15

题目：最小的数是第 0 小。

by Enthon_Yuan @ 2022-07-12 11:50:58

输入k之后k+1就可以了，而且这道题不用分治？

by ben090302 @ 2022-07-12 13:41:15

@soyoungsolong 快排时间复杂度炸了。 要分治思想

#include<bits/stdc++.h>
using namespace std;
int a[500000001],n,k;
int find(int l,int r) {
    if(l == r && l == k) return a[k];
    if(l < r) {
        int i = l,j = r;
        int tmp = a[l];
        while(i < j) {
            while(i < j &&a[j] >= tmp) --j;
            if(i < j) swap(a[i],a[j]);
            while(i < j && a[i] <= tmp) ++i;
            if(i < j) swap(a[i],a[j]);
        }
        a[i] = tmp;
        if(i == k) return a[k];
        if(i > k) return find(l,i - 1);
        else return find(i + 1,r);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n>>k;
    k++;
    for(int i = 1;i <= n;i++) cin>>a[i];
    int key = find(1,n);
    cout<<key;
    return 0;
}

无语，真就不看数据范围？ 还有，最小的数是第0小啊