noj 1574求第k小数

Problem I

求第k小数

时限:1000ms 内存限制:10000K 总时限:3000ms

描述:

 

求第k小数

输入:

 

先输入一个小于10000的正整数n,再输入n个整数,最后输入一个小于等于n的正整数k,

输出:

 

输出其中第k小的数。

输入样例:

 


 

5
2 98 34512 8492 1000
2

输出样例:

 


 

98

 

 

#include <iostream>
#include <stdlib.h>
using namespace std;

int a[10000];

int Partition(int i,int j,int a[])
{
    int pivot=a[i];
    while(i<j)
    {
        while(i<j && a[j]>=pivot)   j--;
        a[i] = a[j];
        while(i<j && a[i]<=pivot)   i++;
        a[j] = a[i];
    }
    a[i] = pivot;
    return i;
}


void find_x(int i,int j,int a[],int x)
{
    if(i<j)
    {
        int pivot = Partition(i,j,a);
        if(pivot == x)  cout<<a[pivot]<<endl;
        else if(pivot>x) find_x(i,pivot-1,a,x);
        else find_x(pivot+1,j,a,x);
    }
}

int main()
{
    int n,k;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>a[i];
    }
    cin>>k;
    //QuickSort(0,n-1,a);
    //cout<<a[k-1]<<endl;
    find_x(0,n-1,a,k-1);
    return 0;
}

 

上一篇:noj 1018 选太子 (约瑟夫问题变种)


下一篇:char 类型中单引号的意义