7-6 sdut-C语言实验-第X大的数
分数 20
全屏浏览
切换布局
作者 马新娟
单位 山东理工大学
X最近爱上了区间查询问题，给出N (N <= 100000) 个数，然后进行M (M <= 50) 次询问，每次询问时，输入一个数X (1 <= X <= N)，输出N个数中第X大的数。
###输入格式:
首先输入一个整数N，代表有N个数，下面一行包含N个整数，用空格隔开。然后为一个整数M，代表有M次询问，下面的M行，每行一个整数X。
###输出格式:
输出N个数中第X大的数。
###输入样例:
1. 4 2. 1 2 2 3 3. 4 4. 1 5. 2 6. 3 7. 4
###输出样例:
1. 3 2. 2 3. 2 4. 1
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
#include<stdio.h> #include<stdlib.h> void Quick_sort(int a[], int l, int r){ if(l >= r) return ; int i = l - 1, j = r + 1, x = a[l + r >> 1]; while(i < j){ do i++; while(a[i] < x); do j--; while(a[j] > x); if(i < j){ int t = a[i]; a[i] = a[j]; a[j] = t; } } Quick_sort(a, l, j), Quick_sort(a, j + 1, r); } int a[100066]; int main() { int n, k, x; scanf("%d", &n); for(int i = 0; i < n; i++){ scanf("%d", &a[i]); } Quick_sort(a, 0, n - 1); scanf("%d", &k); while(k--){ scanf("%d", &x); printf("%d\n", a[n - x]);//max } return 0; }
