HDU 6231(二分&双指针)
分为几个步骤：
1.二分枚举答案
2.对于每个枚举的答案 x x x找到有多少个区间的第 k k k大 ≥ x \ge x ≥x
瓶颈之处在于步骤2.
我们需要在 O ( n ) O(n) O(n)内求出来。
若一个区间的第 k k k大 ≥ x \ge x ≥x，则说明至少有 k k k个数 ≥ x \ge x ≥x。
考虑双指针。
枚举 l l l，然后找到刚好出现 k k k个数 ≥ x \ge x ≥x的位置 r r r，然后此位置 l l l的答案是： n − r + 1 n-r+1 n−r+1。
显然当 l l l递增时， r r r是非递减的。
所以双指针是正确的。
总的时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
// Problem: B - K-th Number // Contest: Virtual Judge - 2017CCPC 哈尔滨 [Cloned] // URL: https://vjudge.net/contest/#problem/B // Memory Limit: 262 MB // Time Limit: 1000 ms // Date: 2021-05-04 23:47:41 // --------by Herio-------- #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define PII pair<int,int> #define fi first #define se second #define pb emplace_back #define SZ(a) (int)a.size() #define IOS ios::sync_with_stdio(false),cin.tie(0) void Print(int *a,int n){
for(int i=1;i<n;i++) printf("%d ",a[i]); printf("%d\n",a[n]); } int a[N]; int n,k; ll m; bool ck(int x){
int c=0,r=1; ll s=0; for(int l=1;l<=n;l++){
while(r<=n&&c<k){
if(a[r]>=x) c++; r++; } if(c==k) s+=n-r+2; if(a[l]>=x) c--; } return s>=m; } 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=0,r=1e9,ans; while(l<=r){
int mid=l+r>>1; if(ck(mid)) l=mid+1,ans=mid; else r=mid-1; } printf("%d\n",ans); } return 0; } 讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/34352.html