HDU6231 K-th Number(技巧二分+尺取)

hdu6231

根本想不到啊…

题意

在所有区间长度大于$k$的区间选出第$k$大的数加入数组$b$

问最后数组$b$的第$m$大

做法

枚举区间计算复杂度上天

但是可以二分计算答案

二分$mid$,假设最后的答案大于等于$mid$就返回$true$

怎么$check?$

二分之后,每个数要么大于等于$mid$,要小于$mid$

我们想求有多少区间的第$k$大比$mid$大

维护$l,r$指针尺取区间

如果$a_i>=mid$,计数器加一

当计数器到达$k$时,说明包含当前区间的区间的第$k$大一定大于等于$mid$

所以计算$ans$

这样通过尺取的手段,就得到了$ans$,也就是多少个区间的第$k$大比$mid$还大

如果$ans>=m$,说明答案确实大于等于$mid$

否则,说明答案小于$mid$

#include <bits/stdc++.h> using namespace std; #define int long long const int maxn=2e5+10; int n,k,a[100009],m; bool isok(int x) { int ans=0,num=0,j=1; for(int i=1;i<=n;i++) { if( a[i]>=x ) num++; if( num==k )//说明区间第k大是大于x的 { ans+=n-i+1;//右端点的取值 while( a[j]<x )//移动左端点 ans+=n-i+1,j++; num--,j++; } } if( ans>=m ) return true; return false; } signed main() { int t; cin >> t; while( t-- ) { cin >> n >> k >> m; int l=1e9+1,r=0; for(int i=1;i<=n;i++) { cin >> a[i]; l = min(l,a[i]); r = max(r,a[i]); } int ans=0; while( r>=l ) { int mid = l+r>>1; if( isok(mid) ) l=mid+1,ans=mid; else r=mid-1; } cout << ans << '\n'; } }