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_bound
和 upper_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; } 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); }
|