第X大的数

亦凉 2022-07-03 14:55 129阅读 0赞

###     ###

### 第X大的数 ###

Time Limit: 1000MS  Memory Limit: 65536KB

[Submit][] [ Statistic][Statistic]

#### Problem Description ####

X最近爱上了区间查询问题，给出N (N <= 100000) 个数，然后进行M (M <= 5) 次询问，每次询问时，输入一个数X (1 <= X <= N)，输出N个数中第X大的数。

#### Input ####

多组输入。

每组首先输入一个整数N，代表有N个数，下面一行包含N个整数，用空格隔开。然后为一个整数M，代表有M次询问，下面的M行，每行一个整数X。

#### Output ####

输出N个数中第X大的数。

#### Example Input ####

4
    1 2 2 3
    4
    1
    2
    3
    4

#### Example Output ####

3
    2
    2
    1

#### Hint ####

#### Author ####

zmx

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int qort(int a[],int left ,int right)
    {
        int x=a[left],i=left,j=right;
    
        while(i<j)
        {
            while(i<j&&a[j]<=x)j--;  ///遇到后才换
            a[i]=a[j];  /// 前移
            while(i<j&&a[i]>=x)i++;
            a[j]=a[i];  /// 后移
        }
        a[i]=x;
        return i;
    }
    int find_k(int a[],int left ,int right, int k)
    {
        int y;
        if(left<=right)
        {
            y=qort(a,left,right);///一次划分函数
            if(y==k)
                return a[y];
            if(y<k)
                return (find_k(a,y+1,right,k));
           else
                return (find_k(a,left,y-1,k));
        }
    }
    
    int main()
    {
        int i,n,m,a[10001],k,x;
        while(~scanf("%d",&n))
        {
            for(i=1; i<=n; i++)
                scanf("%d",&a[i]);
              scanf("%d",&m);
              while(m--)
              {
                  scanf("%d",&k);
                  x=find_k(a,1,n,k);
                  printf("%d\n",x);
              }
    
        }
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2026/pid/2748.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2026/pid/2748.html