归并为什么也T了??

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

Durancer @ 2020-09-30 10:47:17

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int n,a[100009],num[100009];
void Sort(int ls,int lr,int rs,int rr)
{
    int p1=ls,p2=rs,p=ls-1;
    while(p1<=lr&&p2<=rr)
    {
        if(a[p1]<=a[p2])
        {
            num[++p]=a[p1];
            p1++;
        }
        if(a[p1]>a[p2])
        {
            num[++p]=a[p2];
            p2++;
        }
    }
    while(p1<=lr)
    {
        num[++p]=a[p1];
        p1++;
    }
    while(p2<=rr)
    {
        num[++p]=a[p2];
        p2++;
    }
    for(int i=ls;i<=rr;i++)
    {
        a[i]=num[i];
    }
}
void search(int x,int y)
{
    if(x==y)
    return;
    int mid=(x+y)>>1;
    search(x,mid);
    search(mid+1,y);
    Sort(x,mid,mid+1,y);
}
int main()
{
    int k;
    cin>>n>>k;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    search(1,n);
    cout<<a[k+1];
}

by Durancer @ 2020-09-30 10:52:02

用快读还会T一个点


by 星空舞涵 @ 2020-09-30 10:56:55


by 时律 @ 2020-09-30 12:10:22

这题正解是 O(n) 啊


|