NC14301 K-th Number

K-th Number

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

题目大意

给定长为 的序列,求其所有长度 的子区间的第 大数,所构成多重集的第 大数。

题解

二分。

现判定 。问题转化为求第 大数 的子区间个数,若其 则判定失败,否则判定成功。

如果将原始序列转化为一个 01 序列,某位置上为 表示原始序列上这个位置的数 ,否则为 ,那么区间个数就等于为该 01 序列中子区间和 的区间个数。这个显然是可以用尺取法计算的。

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, k;
ll m;
int a[100005], b[100005];
void init(){
    n = read(), k = read();
    scanf("%lld", &m);
    for (int i = 1; i <= n; ++i)    
        a[i] = read(), b[i] = a[i];
    sort(b + 1, b + n + 1);
}
bool judge(int x){
    ll res = 0;
    for (int i = 1, cur = 0, cnt = 0; i <= n; ++i){
        while (cur < n && cnt < k){
            ++cur;
            if (a[cur] > x) ++cnt;
        }
        if (cur == n && cnt < k) break;
        res += (n - cur + 1);
        if (a[i] > x) --cnt;
    }
    return res < m;
}
void solve(){
    int l = 1, r = n;
    while (r > l){
        int mid = (l + r) >> 1;
        if (judge(b[mid]))
            r = mid;
        else l = mid + 1;
    }
    printf("%d\n", b[l]);
}
int main(){
    int T = read();
    while (T--){
        init();
        solve();
    }
    return 0;
}

小结

有的时候二分判定的不仅仅是一个答案,还可以是一个答案区间。

这个大部分时候都是显然的,但是有的时候会忽略。

全部评论

相关推荐

吐泡泡的咸鱼:我也工作了几年了,也陆陆续续面试过不少人,就简历来说,第一眼学历不太够,你只能靠你的实习或者论文或者项目经历,然后你没有论文,没有含金量高的比赛和奖项,只能看实习和项目,实习来说,你写的实习经历完全不清楚你想找什么工作?行研?数据分析?且写的太少了,再看项目,这些项目先不说上过大学读过研究生的都知道很水,然后对你想找的岗位有什么帮助呢?项目和实习也完全不匹配啊,你好像在努力将你所有的经历都放在简历里想表现你的优秀,但是对于你想找的岗位来说,有什么用呢?最后只能获得岗位不匹配的评价。所以你需要明白你想要找的岗位要求是什么,是做什么的,比如产品经理,然后再看你的经历里有什么匹配的上这个岗位,或者对这个岗位以及这个岗位所在的公司有价值,再写到你的简历上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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