ACdream 1099求第k大

 1 /*************************************************************************
 2     > File Name: Kth.cpp
 3     > Author: Stomach_ache
 4     > Mail: sudaweitong@gmail.com
 5     > Created Time: 2014年08月02日 星期六 12时32分04秒
 6     > Propose: ACdream
 7  ************************************************************************/
 8 //输入挂+快速选择
 9 #include <cmath>
10 #include <string>
11 #include <cstdio>
12 #include <fstream>
13 #include <cstring>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 
18 int n, k;
19 int a[5000002];
20 
21 int read() {
22       int x = 0;
23     char ch = ‘ ‘;
24     while (ch < ‘0‘ || ch > ‘9‘) ch = getchar();
25     while (ch >= ‘0‘ && ch <= ‘9‘) x = x * 10 + ch - ‘0‘, ch = getchar();
26     return x;
27 }
28 
29 int sort(int l, int r) {
30       if (l >= r) return a[l];
31       int pivot = a[(l+r)/2];
32     int i = l, j = r;
33     for ( ; ; ) {
34           while (i < j && a[i] <= pivot) i++; 
35         while (i < j && a[j] >= pivot) j--;
36         if (i < j) swap(a[i], a[j]);
37         else break;
38         i++; j--;
39     }
40     swap(a[i], a[(l+r)/2]);
41     if (i == k) return a[i];
42     if (i < k) return sort(i+1, r);
43     else return sort(l, i-1);
44 }
45 
46 int main(void) {
47       while (~scanf("%d %d", &n, &k)) {
48           for (int i = 1; i <= n; i++) 
49               a[i] = read();
50         k = n - k + 1;
51         int ans = sort(1, n);
52         printf("%d\n", ans);
53     }
54     return 0;
55 }