每日一题K-th Number
K-th Number
https://ac.nowcoder.com/acm/problem/14301
额没开long long wa了30%
说实话这道题不看二分这个这个标题我是真的想不到
题目大意:给一个长度为N的数组A 从A中找区间取他的第K大值加入开始为空的数组B(如果区间长度小于K,则此区域舍去)求出最后的B数组的第K大元素值
请在这里输入引用内容
输入:给t组数据,每一组开头包含一个n,k,m
分别代表数组A的长度 A的第K大值 数组B的第M大值
思路:首先二分一个元素值假设为X,每次从A中寻找含有大于等于x的值,如果找到的区间内满足前面条件的值的总数大于k,则该区间就可以找到第K大的数,可以想到如果这些区间总数小于M个,则肯定取不到第M小,所以可以根据此来当二分判断条件 满足说明区间,有多X小了,如果刚好的最优解就是答案。
找区间就用尺取法,两个指针l,r。找到第一个大于的区间从前往后找,l开始不动找到满足含K个有效值的区间[1,r]确定好r后把l往左移,此时的r只能往右移
最后别忘记开 long long
#include<bits/stdc++.h> using namespace std; #define ll long long const ll maxn=1e5+7; ll a[maxn]; bool check(ll x,ll n,ll k,ll m) { ll l=0; ll r=0; ll ans=0; ll cnt=0; while (l<=n) { while (ans<k&&r<n)///维护界限 右移 { if (a[++r]>=x) ++ans; } if (ans>=k) { cnt+=(n-r+1); } if (a[++l]>=x)///l开始等于1 左移 --ans; } if (cnt>=m) return 1; return 0; } int main() { ll t; scanf("%lld",&t); while (t--) { ll n,k,m;///总数 A数组第k大 B数组第m大 scanf("%lld%lld%lld",&n,&k,&m); for (int i=1;i<=n;++i) { scanf("%lld",a+i); } ll l=1; ll r=maxn;///二分范围 while (l<=r) { ll mid=(l+r)/2; if (check(mid,n,k,m)) l=mid+1; else r=mid-1; } printf("%lld\n",l-1); } return 0; }