题目: NC14301 K-th Number ,哈哈,我们今天来看一道有点思维难度的题嘛,这是选自牛客上的一道题,好了,我们一起来看看题意吧:
考虑到直接复制题目,或者截屏的方式不是很方便阅读,我就把直接题目链接放下面!
题目传送门: NC14301 K-th Number
思路
:
我们直接二分答案求解B中的第m大的数,假设答案为x,在A数组中,求解得到
第K大数大于x的区间
为cnt,若cnt>m-1,则说明x取小了!
我们来看看成功AC的代码吧:
#include<bits/stdc++.h> using namespace std; #define ll long long int t,n,k; ll m;//这里记住开long long int a[100010]; int l,r; int check(int x){ ll cnt=0,s=0;//这里也要开long long for(int i=1,j=1;i<=n;i++){ //i是右指针, j是指针 if(a[i]>=x) cnt++; if(cnt==k){ s+=n-i+1;//把右边的全部算进来 while(a[j]<x) s+=n-i+1,j++;//只要这个区间 大于x的数不少于k,左指针就可以右移 cnt--,j++; } } return s>m-1; } int main(){ ios::sync_with_stdio(false); cin>>t; while(t--){ cin>>n>>k>>m; memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) cin>>a[i]; l=0,r=0x3f3f3f3f; while(l<r){//二分模板 ll mid=(l+r+1)>>1; if(check(mid)) l=mid; else r=mid-1; } cout<<l<<"\n"; } return 0; }