求助-来自暴龙

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 coin_sir @ 2022-02-11 10:38:22

@int32 题目不让的,那样作弊吧。。。


by hjxhjx @ 2022-02-11 10:38:47

@coin_sir 请学习 nth_element 的原理


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

@hjxhjx 我去试试


by tctd613 @ 2022-02-11 17:05:56

@peppa_hao 用sort会超时


by Rose_Lu @ 2022-02-11 17:22:01

@coin_sir 我名字你都打错了,还是不是朋友了


by Rose_Lu @ 2022-02-11 20:01:34

@tctd613 o谢谢(#^.^#)


by tctd613 @ 2022-02-12 11:47:05

@peppa_hao 不谢不谢(#^.^#)


上一页 |