自己写的judge函数太丑了,还是错的
//类似滑动窗口
bool judge(int x){
int ans=0;int i;int cnt=0;
for (i=1;i<=n;i++)
{
if(a[i]>=x) cnt++;
if (cnt>=k) break;
}
ans+=n-i+1;
int j=1;
while (i<=n)
{
while (j<=n&&a[j]<x){
ans+=n-i+1;
j++;
}
while (a[i]<x) i++;
}
return ans<x;
}
正解代码
#include<cstdio>
using namespace std;
typedef long long ll;
int n,k;
ll m;
int a[100005];
bool judge(int x){
int ans=0;int i;int cnt=0;
for (i=1;i<=n;i++)
{
if(a[i]>=x) cnt++;
if (cnt>=k) break;
}
ans+=n-i+1;
int j=1;
while (i<=n)
{
while (j<=n&&a[j]<x){
ans+=n-i+1;
j++;
}
while (a[i]<x) i++;
}
return ans<x;
}
int main(){
int T;
scanf("%d",&T);
while (T--){
scanf("%d%d%lld",&n,&k,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
int l=1,r=10000000000;
int mid;
while (l<r){
mid=(l+r)>>1;
if (judge(mid)) l=mid+1;
else r=mid;
}
printf("%d\n",l-1);
}
return 0;
}