求助-来自暴龙

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

coin_sir @ 2022-02-11 10:25:11

#include<bits/stdc++.h>
using namespace std;
int pai(int, int);
int a[5000001];
int k;int n;
int main()
{
   cin>>n>>k;
   for(int cs=1;cs<=n;cs++)
   {
       cin>>a[cs];
   }
   pai(1,n);
} 
int pai(int z,int y)
{
    int mid,l,r;
    mid=a[(z+y)/2];l=z;r=y;
        do
        {
            while(a[l]<mid)
        l++;
            while(a[r]>mid)
        r--;
            if(l<=r)
        {
            swap(a[l],a[r]);
            l++;r--;//即使发生交换,l,r的变化不能停止
        }
        }   while(l<=r);
    if(k<=r) pai(y,r);
    else if(l<=k) pai(l,z);
    else {
    cout<<r<<" "<<l<<a[r]<<a[r+1]<<"标记"<<endl;cout<<a[r+2]<<endl;return 0;}
}

by Rose_Lu @ 2022-02-11 10:29:29

这题用sort排一下就行了


by coin_sir @ 2022-02-11 10:30:46

救命,我把能想到的都想到了!!!!


by Liquefyx @ 2022-02-11 10:31:22

@coin_sir ???可以详细描述一下你遇到的问题qwq


by coin_sir @ 2022-02-11 10:31:23

@peppa_hao 60分。。。


by coin_sir @ 2022-02-11 10:32:29

@RJ一个 测试数据对。提交不对


by Liquefyx @ 2022-02-11 10:33:41

@coin_sir 学这个


by coin_sir @ 2022-02-11 10:36:05

@RJ一个 sort吗?


by coin_sir @ 2022-02-11 10:36:34

@RJ一个 sort会超时得60分的好成绩


by int32 @ 2022-02-11 10:37:51

@coin_sir 请学习 nth_element


by coin_sir @ 2022-02-11 10:37:51

@peppa_hao 卢浩洋sort你又不是没试过,我要真是个陌生人信了你的鬼话。。。。。那不得浪费一天


| 下一页