[排序]求解第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大的分值为多少。

示例

输入

2

3 2

1 2 3

3 1

4 2 1

输出

1

2

题解:

首先将这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大的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!