2020 CCPC-Wannafly Winter Camp Day 1 F

Problem F. 乘法

Statement

给两个长度分别为 $n,m$ 的数列 $A, B$ 来表示一个 $n \times m$ 的矩阵 $C$(即 $C_{i,j} = A_i \cdot B_j$)。 给出整数 $K$,你需要求出 $C$ 中第 $K$ 大的数。

$1 \leq n,m \leq 10^5$, $1 \leq K \leq n \times m$

$-10^6 \leq A_i,B_i \leq 10^6$

Solution

$O(n \log m \log (\max C_{i,j} - \min C_{i,j}))$ 的做法显然吧……

我们预先对每一行排好序。对于一个假定的答案 $mid$,我们可以 $O(n)$ 枚举行,对于每一行都 $O(\log m)$ 二分一下计算有多少个数大于 $mid$,就能 $O(n \log m)$ 计算 $mid$ 是第几大。又因为 $mid$ 与其位次是单调的关系,那么考虑二分答案 $mid$,就可以 $O(n \log m \log (\max C_{i,j} - \min C_{i,j}))$ 求 $K$ 大了。

二分这种东西需要注意一下细节,尤其是这题还有负数和 $0$……我开场读的第一题就是这个,一眼就会了,以为有希望抢一血,结果是被 lower_boundupper_bound 演了很久,调了一个小时……太丢人了……

Code

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
ll a[N], b[N];
ll n, m, k;

ll getrank (ll cur) {
ll rank = 0;
for (int i = 1;i <= n;i++) {
ll pos;
if (a[i] == 0) pos = (cur <= 0) ? m : 0;
if (a[i] > 0) pos = m - (lower_bound(b + 1, b + m + 1, (double)cur / a[i]) - (b + 1));
if (a[i] < 0) pos = upper_bound(b + 1, b + m + 1, (double)cur / a[i]) - (b + 1);
rank += pos;
//cout << "L" << i << ':' << pos << endl;
}
return rank + 1;
}

int main () {
scanf("%lld%lld%lld", &n, &m, &k);
for (int i = 1;i <= n;i++) {
scanf("%lld", &a[i]);
}
for (int i = 1;i <= m;i++) {
scanf("%lld", &b[i]);
}
sort(b + 1, b + m + 1);

ll l = -1e12, r = 1e12;
while (l <= r) {
ll mid = (l + r) / 2;
ll rank = getrank(mid);
if (rank > k) l = mid + 1;
else r = mid - 1;
}
printf("%lld", r);
}