秦皇岛网站设计营销型网站的推广方法
补充习题: 第k小的数
问题描述
有两个正整数数列,元素个数分别为 N N N和 M M M.从两个数列中分别任取一个数相乘,这样一共可以得到 N × M N\times M N×M个数,询问这 N × M N\times M N×M个数中第 K K K小的数是多少.
- 数据范围:
N , M < = 200000 , K < = 2.1 ∗ 1 0 10 , A i < = 1 0 9 ; N,M<=200000,K<=2.1*10^{10},A_i<=10^9; N,M<=200000,K<=2.1∗1010,Ai<=109;
solution
∵ a > b , c > d \because a>b, c>d ∵a>b,c>d
∴ a × c > b × d \therefore a \times c > b \times d ∴a×c>b×d
设本题中的两个数组分别为 a 和 b 设本题中的两个数组分别为a和b 设本题中的两个数组分别为a和b
∴ 可知 , 若 a i × b j < K \therefore 可知,若a_i\times b_j < K ∴可知,若ai×bj<K
则 a i − 1 , i − 2 , . . . , 1 ∗ b j , j − 1 , . . . , 1 < K 则a_{i-1,i-2,...,1} * b_{j,j-1,...,1} < K 则ai−1,i−2,...,1∗bj,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;
}