soj3102第k小的数.cpp

来自「一些ACM题目的解答,主要是soj和poj的」· C++ 代码 · 共 54 行

#include<stdio.h>

#define MAX 2000004

int c[MAX],a[MAX],b[MAX];

char dsa[MAX*10+32];

int ksmall(int k,int *array,int n,int *p,int *q)
{
    int h=0,g=0;
    int temp=array[k-1];
    array[k-1]=array[0];
    array[0]=temp;
    for(int i=1;i<n;i++)
    {
        if(array[i]>array[0])
            q[g++]=array[i];
        else
            p[h++]=array[i];
    }
    if(h==k-1)
        return array[0];
    else if(h>k-1)
        return ksmall(k,p,h,q,array);
    else
        return ksmall(k-1-h,q,g,p,array);
}

int main(void)
{
    int n,k;
    while(scanf("%d%d",&n,&k)==2)
    {
        getchar();
        gets(dsa);
        int windy=0,YUMEN=0;
        for(int i=0;dsa[i]!='\0';i++)
        {
            if(dsa[i]==' ')
            {
                c[windy++]=YUMEN;
                YUMEN=0;
            }
            else
                YUMEN=YUMEN*10+dsa[i]-48;
        }
        c[windy++]=YUMEN;
        printf("%d\n",ksmall(k,c,n,a,b));
    }
    return 0;
}