NC14301 K-th Number

简介: NC14301 K-th Number

题目: 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;
}


相关文章
|
6月前
K-th Number(尺取)
K-th Number(尺取)
43 0
ACM刷题之路(十九)二分+尺取 2019暑期集训 HDU6231 K-th Number
ACM刷题之路(十九)二分+尺取 2019暑期集训 HDU6231 K-th Number
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
98 1
|
5月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
6月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
43 0
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
39 0
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
94 0
LeetCode 414. Third Maximum Number
|
存储
LeetCode 313. Super Ugly Number
编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
95 0
LeetCode 313. Super Ugly Number
|
算法
LeetCode 306. Additive Number
累加数是一个字符串,组成它的数字可以形成累加序列。 一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。 给定一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是累加数。 说明: 累加序列里的数不会以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
121 0
LeetCode 306. Additive Number