【9205】军事机密

Time Limit: 2 second
Memory Limit: 32 MB

问题描述
我军方截获的信息由n（n≤30000）个数字组成，因为是敌国的高端秘密，所以一时不能被破获。最原始的想法就是对这n个数进行从小到大排序，每个数都对应一个序号，然后对第i个是什么数感兴趣，现在要求编程完成。

Input

第一行是n，第二行是n个截获的数字，第三行是数字k，接着是k行要输出数的序号。

Output

k行序号所对应的数字。

Sample Input

5
121 1 126 123 7
3
2
4
3

Sample Output

7
123
121

【题解】

先把数字快排，从小到大排，一遍，然后对于输入的i，输出a[i]就可以了。这题就是拿来练快排的。啦

【代码】

#include <cstdio>

int n,a[30001];

void input_data()
{
    scanf("%d",&n); //输入n个数据
    for (int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
}

void kp(int l,int r) //进行快排
{
    int i = l,j = r,m = a[(i+j)/2];
    do
    {
        while (a[i] < m) i++;
        while (m < a[j]) j--;
        if (i <= j)
        {
            a[0] = a[i];a[i] = a[j];a[j] = a[0];
            i++;j--;
        }
    }
    while (i <= j);
    if (l < j) kp(l,j);
    if (i < r) kp(i,r);
}

void output_ans() //对于提问输出相应位置的数字就好了
{
    int k;
    scanf("%d",&k);
    for (int i = 1;i <= k;i++)
        {
            int m;
            scanf("%d",&m);
            printf("%d
",a[m]);
        }
}

int main()
{
    input_data();
    kp(1,n);
    output_ans();
    return 0;
}