第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 
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48