A61157. NOIP2008年普及组初赛完善程序题：(找第k大的数) 给定一个长度为1,000,000的无序正整数序列, 以及另一个数n (1<=n<=1000000), 然后以类似快速排序的方法找到序列中第n大的数（关于第n大的数：例如序列{1，2，3，4，5，6}中第3大的数是4）。#include <iostream>

NOIP2008年普及组初赛完善程序题：(找第k大的数) 给定一个长度为1,000,000的无序正整数序列, 以及另一个数n (1<=n<=1000000), 然后以类似快速排序的方法找到序列中第n大的数（关于第n大的数：例如序列{1，2，3，4，5，6}中第3大的数是4）。

#include <iostream>
usingnamespacestd;
int a[1000001],n,ans = -1;
void swap(int &a,int &b)
{
    int c;
    c = a; a = b;    b = c;
}

int FindKth(int left, int right, int n)
{
    int tmp,value,i,j;
    if (left == right) return left;
    tmp = rand()% (right - left) + left;
    swap(a[tmp],a[left]);
    value =[       ①       ];
    i = left;
    j = right;
    while (i < j)
    {
        while (i < j && [       ②       ]) j --;
        if (i < j) {a[i] = a[j]; i ++;} elsebreak;
        while (i < j && [       ③     ]) i ++;
        if (i < j) {a[j] = a[i]; j - -;} elsebreak;
    }
    [      ④       ]  
    if (i < n) return  FindKth([         ⑤        ] );
    if (i > n) return [         ⑥           ]        
    return i;
}

int main()
{
    int i;
    int m = 1000000;
    for (i = 1;i <= m;i ++)
        cin >> a[i];
    cin >> n;
    ans = FindKth(1,m,n);
    cout << a[ans];
    return0;
}