[排序]求解第k大分值

描述：

Arch0n老师is a rich man, 他靠自己的才华和智商年纪轻轻就赚了不少钱。为了训练自己的智商，他经常玩一些interesting的游戏来训练自己的智商，比如什么RGB游戏，还有和妹子一块玩Don’t Starve。

言归正传，今天他又发明了一个新的interesting game。Ar老师手上有一堆卡牌，然后卡牌上写了一个数字Ai(正整数)，当前他有n张牌，然后他总是随机取出两张来，然后他一眼就能看出这两牌中哪一张小（相同就取相同的，这操作好像对于Ar老师来说太简单了），作为这两张牌的有效分值，然后呢他陷入了沉思，对于n张牌取两张牌显然有确定的组合可能性，有n(n-1)/2对组合，然后他想知道所有这些组合中第k大的分值是多少。输入描述:输入一个t表示数据组数；(0<t<=10)接下来一行是n,k,表示n张牌和最后第k大的分值；（1<n<2500,保证0<k<=n(n-1)/2）接下来一行是n个值ai，表示第i张牌上的数字(0 < ai <= 10000000)。输出描述:每组数据输出一行，即第k大的分值为多少。

示例

输入

3 2

1 2 3

3 1

4 2 1

输出

题解：

首先将这n个数进行从大到小排序，a[0]储存第1大，a[1]储存第2大……第2个和第1个比较最小的是第2个，第3个和前两个比较较小的均是第3个，第4个和前3个比较均是第4个，以此递推，第n个数和n前n-1个比较均是n较小。将所有情况全排列很容易超时，因此我们可以从第k大这个k下手。由于a[0]最大，因此a[0]和任意比较都不会输出a[0]。那么首先k为1输出a[1],1<k<=1+2输出a[2],1+2<k<=1+2+3输出a[3]……现在应该很清楚了吧。可以设置一个变量cnt，和i,从1开始，cnt每次加1，i每次加cnt，直到i加到比k大或者等于时，那么此时的a[cnt]就是第k大的数。

#include<iostream>  
#include<algorithm>  
int cmp(int a, int b) {  
    return a > b;  
}  
int T, N, k, a[100010];  
using namespace std;  
int main() {  
    cin >> T;  
    while (T--) {  
        cin >> N >> k;  
        for (int i = 0; i < N; i++) {  
            cin >> a[i];  
        }  
        sort(a, a + N, cmp);  
        int cnt = 1, i = 1;  
        for (int i = 1; i < k; i += cnt) {  
            cnt++;  
        }  
        cout << a[cnt] << endl;  
    }  
    return 0;  
}