第K大数 双指针

K-th Number

https://ac.nowcoder.com/acm/problem/14301

题意

组数据。
每组数据给定长度为 的数组 ,对所有长度大于等于 的连续子段,取出其第 大放入数组 中。
求数组 的第 大。

思路

题意非常绕但是是非常好的一道题。

对于一个序列,我们如果添加进一个新数进去后,其中第大数一定不会减小。

这正是为什么可以sum += n - R + 1;加上右边所有的区间总数。

考虑对值二分,然后找有多少个区间的第大可以是,只要满足的区间数量大于就返回。这个值很可能是小的,然后就二分向右逼近。

函数的详细注释:

bool check(int x) {
    ll cnt = 0, sum = 0;  //找有多少个区间的第k大可以是x
    for (int L = 1, R = 1; R <= n; ++R) {
        if (a[R] >= x) cnt++;
        if (cnt == k) {
            sum += n - R + 1;//右边的每一个区间都可以满足条件
            while (a[L] < x) sum += n - R + 1, ++L;
            //只要比x大的数不少于k个,左指针逐级右移,都不影响,都是满足的区间
            L++;//抛弃左指针指向的元素
            cnt--;
        }
    }
    return sum >= m;
}

solution

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
typedef long long ll;
ll m, n, k, a[maxn];
bool check(int x) {
    ll cnt = 0, sum = 0;
    for (int L = 1, R = 1; R <= n; ++R) {
        if (a[R] >= x) cnt++;
        if (cnt == k) {
            sum += n - R + 1;
            while (a[L] < x) sum += n - R + 1, ++L;
            L++;
            cnt--;
        }
    }
    return sum >= m;
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld%lld%lld", &n, &k, &m);
        ll left = 1, right = 1, ans;
        for (int i = 1; i <= n; i++)
            scanf("%lld", &a[i]), left = min(left, a[i]), right = max(a[i], right);
        while (left <= right) {
            int mid = (left + right) / 2;
            if (check(mid))
                ans = mid, left = mid + 1;
            else
                right = mid - 1;
        }
        printf("%lld\n", ans);
    }
}

reference

https://blog.nowcoder.net/n/11a6a92bb91a4710b47d09fe936c75e1

https://blog.nowcoder.net/n/3a1dad4a9e4f4ac2993fa2d8e0e6c77f

算法竞赛之路 文章被收录于专栏

整理、记录算法竞赛的好题

全部评论

相关推荐

06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
机械打工仔:不管啥专业,找工作改简历的第一课先把你那排版改了,简历上不要写个人简历四个字,找你要简历的谁不知道这个是简历?而且还占那么多空间,直接把自己名字和基础信息写上面,整体字体大一些。 还有这种经典两页简历一页大空白,导出PDF的时候多了一页几乎全是白的你自己看着不难受吗随手的事为啥不能改掉呢,这是态度问题,你试想一下你是HR你打开简历看到格式都没调整过会是什么感受?你自己都不重视你的简历,HR更不会在意。 然后内容你那个做两年咖啡就别往里写了,简历在精不在多,你在往你的简历里打字的时候就要想好这东西对你要找的工作有没有帮助。自我评价写一行就行了,不如给专业技能单开一栏。核心课程均分90这个真别写了,把你上过的有用的专业课列出来也行。有很多地方废话很多的精炼一下,比如你校内项目第一个写的那些,全然没有重点。 好好修改一下,我看你内容也挺优秀的,别被一个随便做的简历耽误了,我一个同专业的打工人看了都揪心更别说一天看几百份简历的HR
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务