第K小数

//好久前做过的样子 但是看了又完全忘记了 还是写一写 在自己变得更蠢之前

Solution:

大意是给给定n个数和m个数 两组数两两相乘 求出第k大的数
首先想到二分 然后考虑检验 暴力不是很妙妙 考虑对两个数组排序 这样是不会影响到结果的 但是却会带来单调性 因为满足小于k的乘积里 第一组数从小到大 第二组一定会从大到小 然后就OK啦

Code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 200001;
int n, m, k, a[N], b[N];
inline int read() {
    int x = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') w = 1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return w ? - x : x;
}
inline bool judge(int tmp) {
    int now = 0;
    for(int i = 1, j = m; i <= n; ++ i, now += j)
        while(a[i] * b[j] > tmp) -- j;
    return now >= k;
}
signed main() {
    n = read(), m = read(), k = read();
    for(int i = 1; i <= n; ++ i) a[i] = read();
    for(int j = 1; j <= m; ++ j) b[j] = read();
    sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + m);
    int l = 1, r = a[n] * b[m], ans;
    while(l < r) {
        int mid = (l + r) >> 1;
        //printf("---%d\n", mid);
        if(judge(mid)) r = mid, ans = mid;
        else l = mid + 1;
    }
    printf("%lld", ans);
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注