题意
给定一个长度为 $n$ 的整数数列 $a_1,a_2,…,a_n$ 和一个长度为 $m$ 的整数数列 $b_1,b_2,…,b_m$。 利用上述两个数列构造出一个 $n\times m$ 的整数矩阵 $c$ , 其中 $c_{i,j}=a_i×b_j$ 。给定整数 $k$ ,请你计算将矩阵中所有 $n\times m$ 个元素从大到小排序后的第 $k$ 个元素的值。其中 $1\le n,m\le 10^5,a_i,b_i\in [-10^6,10^6]$
这题其实思路上并不难,主要的难点其实是在 $a_i,b_i$ 可正可负上面,导致处理起来稍微麻烦一点。
简化版的此题思路
我们先不要管数组可正可负,就先假设数组所有数都是正数,那么我们可以将 $a,b$ 分别排序,然后我们在此之上进行二分答案。第 $k$ 大意味着矩阵中大于等于该答案的数有至少 $k$ 个。那么我们进行类似于 upper_bound
的搜索,找到最小的 $x$ ,使得矩阵中大于等于 $x$ 的数小于 $k$ 个,此时答案是 $k-1$ 。
那么剩下的就是在给定数 $x$ 之后,求矩阵中大于等于 $x$ 的个数有多少了。由于此时所有数都是正数,那么随着 $a$ 从右往左遍历,此时满足条件的最小 $b_i$ 一定是单调递增的。所以我们给 $b$ 设置一个单调递减指针即可。
最后是设置上下界,由于我们的二分查找条件是 lo<hi
,而如果初始的 $a$ 和 $b$ 全部由相同数组成,初始条件就是 lo==hi
了,所以我们把上界设为矩阵最大值+1即可。
复杂度 $O(n\log(\text{hi-lo}))$ ,简化版的提交链接在这里 : [51nod1105] 第K大的数
// cnt of A[i] * B[j] >= x
i64 find(i64 x)
{
i64 ret = 0;
int idx = 0;
for (int i = n - 1; i >= 0 && idx < n; --i)
{
i64 target = (x / A[i]) + (x % A[i] > 0);
while (idx < n && B[idx] < target)
++idx;
ret += (n - idx);
}
return ret;
}
int main()
{
n = rd(), k = rd();
for (int i = 0; i < n; ++i)
A[i] = rd(), B[i] = rd();
sort(A, A + n), sort(B, B + n);
i64 lo = A[0] * B[0], hi = A[n - 1] * B[n - 1] + 1;
while (lo < hi)
{
i64 mi = (lo + hi) >> 1;
if (find(mi) >= k)
lo = mi + 1;
else
hi = mi;
}
wr(lo - 1);
}
回到本题
本题麻烦的核心点就在于数组里的数有正有负,而且查找时传入的 $x$ 也可以有正有负。但是不难发现,在给定了 $x$ 以及 $a_i$ 的正负性之后,$b_i$ 的变化依旧是满足单调性的,只不过此时满足条件的值可能是大于等于或者小于等于。在寻找对应的目标上界/下界时,我们也可以利用C语言特有的负数之间除法对绝对值向下取整的结果来计算。具体的计算方式写在了代码注释当中,我们照常对数组进行排序即可,然后在每次扫描时注意不要越界以及判断 $a_i$ 的正负性以及等于 $0$ 的时候即可。
至于答案的上下界选取,虽然数组都有正有负,但是最大值和最小值一定由 $a,b$ 数组的最大值和最小值构成,只要取这4种可能性的最大值和最小值即可。
于是下面代码就有了,复杂度为 $O((n+m)\log(2\times 10^{12}))$ 。
int main()
{
i64 n = rd(), m = rd(), k = rd();
vector<i64> a(n), b(m);
for (int i = 0; i < n; ++i)
a[i] = rd();
for (int i = 0; i < m; ++i)
b[i] = rd();
sort(a.begin(), a.end()), sort(b.begin(), b.end());
i64 lo = min(min(a[0] * b[m - 1], a[0] * b[0]), min(a[n - 1] * b[m - 1], a[n - 1] * b[0]));
i64 hi = max(max(a[0] * b[m - 1], a[0] * b[0]), max(a[n - 1] * b[m - 1], a[n - 1] * b[0])) + 1;
// return count of a[i] * b[j] >= x
function<i64(i64)> find = [&](i64 x)
{
i64 ret = 0;
if (x >= 0)
{
int a_idx = n - 1, b_idx = 0;
while (a_idx >= 0 && a[a_idx] > 0) // target increase when a[i] decrease (x > 0 && a[i] > 0)
{
// e.g. x = 9, a[a_idx] = 4, target = 3
i64 target = (x / a[a_idx]) + (x % a[a_idx] != 0); // need >= target
while (b_idx < m && b[b_idx] < target)
++b_idx;
ret += (m - b_idx);
--a_idx;
}
while (a_idx >= 0 && a[a_idx] == 0) // a[i] = 0
{
ret += (x == 0) ? m : 0;
--a_idx;
}
b_idx = 0;
while (a_idx >= 0 && a[a_idx] < 0) // target decrease when a[i] decrease (x > 0 && a[i] > 0)
{
// e.g. x = 9, a[a_idx] = -4, target = -3
i64 target = (x / a[a_idx]) - (x % a[a_idx] != 0); // need <= target
while (b_idx < m && b[b_idx] <= target)
++b_idx;
ret += b_idx;
--a_idx;
}
}
else
{
int a_idx = n - 1, b_idx = m - 1;
while (a_idx >= 0 && a[a_idx] > 0)// target decrease when a[i] decrease (x < 0 && a[i] > 0)
{
// e.g. x = -9, a[a_idx] = 4, target = -2
i64 target = (x / a[a_idx]); // need >= target
while (b_idx >= 0 && b[b_idx] >= target)
--b_idx;
ret += (m - 1 - b_idx);
--a_idx;
}
while (a_idx >= 0 && a[a_idx] == 0) // a[i] = 0
ret += m, --a_idx;
b_idx = m - 1;
while (a_idx >= 0 && a[a_idx] < 0) // target decrease when a[i] increase (x < 0 && a[i] < 0)
{
// e.g. x = -9, a[a_idx] = -4, target = 2
i64 target = (x / a[a_idx]); // need <= target
while (b_idx >= 0 && b[b_idx] > target)
--b_idx;
ret += (b_idx + 1);
--a_idx;
}
}
return (i64)ret;
};
while (lo < hi)
{
i64 mi = (lo + hi) >> 1;
if (find(mi) >= k)
lo = mi + 1;
else
hi = mi;
}
wr(lo - 1);
}