第k小的数

补充习题: 第k小的数

问题描述

有两个正整数数列,元素个数分别为$N$和$M$.从两个数列中分别任取一个数相乘,这样一共可以得到$N\times M$个数,询问这$N\times M$个数中第$K$小的数是多少.

• 数据范围:
  $N,M<=200000,K<=2.1\ast 10^{10},A_i<=10^9;$

solution

$\because a>b,c>d$

$\therefore a\times c>b\times d$

$设本题中的两个数组分别为a和b$

$\therefore 可知,若a_i\times b_j<K$

$则a_{i-1,i-2,...,1}\ast b_{j,j-1,...,1}<K$

由此,这一题就好办了.

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int a[200001], b[200001];long long check(int x) {int i = 1;int j = m;long long sum = 0;while(j >= 1 && i <= n) {while(a[i] * b[j] > x) {--j;}sum += j;++i;}return sum;
}int main() {cin >> n >> m >> k;int max1 = -1, max2 = -1;for(int i = 1; i <= n; ++i) {cin >> a[i];max1 = max(max1, a[i]);}for(int i = 1; i <= m; ++i) {cin >> b[i];max2 = max(max2, b[i]);}sort(a + 1, a + n + 1);sort(b + 1, b + m + 1);long long l = 1, r = max1 * max2;long long ans = 0;while(l <= r) {long long mid = (l + r) >> 1;if(check(mid) >= k) {r = mid - 1;ans = mid;}else {l = mid + 1;}}cout << ans << endl;return 0;
}