NC15686. Arch0n's interesting game
描述
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大的分值为多少。
示例1
输入:
2 3 2 1 2 3 3 1 4 2 1
输出:
1 2
C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 492K, 提交时间: 2020-04-04 22:27:12
#include<bits/stdc++.h>
using namespace std;
int t,n,k,a[2502],i,j;
int main(){
cin>>t;
while(t--){
cin>>n>>k;
for(i=0;i<n;++i) cin>>a[i];
sort(a,a+n);
for(j=0;j<n;j++)
if(j*(j-1)/2>=k)break;
cout<<a[n-j]<<endl;
}
}
C++ 解法, 执行用时: 7ms, 内存消耗: 400K, 提交时间: 2022-05-04 10:23:37
#include<bits/stdc++.h>
using namespace std;
int a[2500+10],n,k,t,j;
int main(){
cin>>t;
while(t--){
cin>>n>>k;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(j=1;k>0;k-=j,j++);
cout<<a[n-j]<<endl;
}
}
Python3 解法, 执行用时: 38ms, 内存消耗: 5924K, 提交时间: 2022-08-03 20:14:29
for _ in range(int(input())):
n,k=map(int, input().split())
a=list(sorted(map(int, input().split()),key= lambda x: -x))
print(a[int((2 * k + (2 * k) ** 0.5) ** 0.5)])