C++(g++ 7.5.0) 解法, 执行用时: 118ms, 内存消耗: 768K, 提交时间: 2022-10-16 15:30:12

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100005

int arr[N],n;

// check函数用于计算参数在排名
ll check(int x){
	deque<int> dq;
	ll last=0,ans=0;
	for(int i=1;i<=n;i++){
		if(arr[i]>=x){
			dq.push_front(i);
		}
		if(dq.size()>=2){
			ans+=(dq.back()-last)*(n-i+1);
			last = dq.back();
			dq.pop_back();
		}
	}
	return ans;
}

int main(){
	int test;
	cin>>test;
	while(test--){
		ll k;
		scanf("%d %lld",&n,&k);
		for(int i=1;i<=n;i++){
			scanf("%d",&arr[i]);
		}
		int left=1,right=1e9,ans=0;
		while(right>=left){
			int mid = (left+right)/2;
			if(check(mid)>=k){// 如果mid的排名大于k则mid的值偏小，此时将left的值变为mid+1
				ans=mid;
				left=mid+1;
			}else right = mid-1;
		}
		printf("%d\n",ans);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 201ms, 内存消耗: 1236K, 提交时间: 2020-02-15 16:00:18

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,a[N],num,b[N];
long long k;
long long check(int x)
{
	int j=n;
	long long tot=0;
	num=0;
	for(int i=n;i>=1;--i)
	{
		if(a[i]>x) ++num;
		while(num>1&&j>i) num-=(a[j]>x),--j;
		tot+=j-i;
	}
	return tot;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%lld",&n,&k);
		int ans=2333;
		for(int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i];
		sort(b+1,b+n+1);
		for(int l=1,r=n,mid=(l+r)>>1;l<=r;mid=(l+r)>>1)
		if(1ll*n*(n-1)/2-check(b[mid])<k) ans=mid,r=mid-1;else l=mid+1;
		printf("%d\n",b[ans]);
	}
}