题解 P1138 【第k小整数】

L__A · 2018-09-26 17:39:31 · 题解

今天考试的一道题的部分分里用到了快排O(n)求区间第k大，想来找个模板题写写，就找到了这道题。

先用一个bool数组去掉重复的，如果剩下的数数量小于k，无解。否则通过快排O(n)求剩下的数中第k小的数。

具体方法就是每次快排过程中，小于基准数的放在基准数左边，大于的放在右边，那么考虑，若基准数左边的数的数目p为k-1，那么基准数就是第k小的，如果p>k-1，说明第k小的数在基准数左边，否则在右边，这样每次只递归其中一半来查找，最后复杂度即n+n/2+n/4+...+1=O(n)。

这种做法当然不是最优解，不过也是把这道题当作区间第k大的数的题解来写的。

写的时候还出了很多问题（现在也不知道其中一些问题是为什么XD），这种简单算法还写了这么久……太弱了…

#include <cstdio>
#include <algorithm>

using namespace std;

int n,a[10010],num;
bool vis[30010];

inline char gc()
{
    static char buf[1000001],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2) ? EOF : *p1++;
}

inline void re(int &x)
{
    x=0;
    char ch=gc();
    while(ch<'0'||ch>'9') ch=gc();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48), ch=gc();
}

int qfk(int l,int r,int k)
{
    int i=l,j=r,p,tmp=a[l];
    while(i<j)
    {
        while(a[j]>tmp&&j>i) --j;
        while(a[i]<tmp&&i<j) ++i;
        swap(a[i],a[j]);
    }
    a[i]=tmp;
    p=i-l;
    if(p==k-1) return tmp;
    if(p>k-1) return qfk(l,i-1,k);
    else return qfk(i+1,r,k-p-1);
}

int main()
{
    int i,t,k;
    re(n); re(k);
    for(i=1;i<=n;++i)
    {
        re(t);
        if(!vis[t])
        {
            vis[t]=1;
            a[++num]=t;
        }
    }
    if(k>num) printf("NO RESULT");
    else printf("%d",qfk(1,num,k));
    return 0;
}