解题思路
我们要统计所有配对 (i,j) 中满足 xi×yj≥K 的个数。两个数列均为非负整数,我们可以利用排序和二分查找高效计算。
- 将传感器 Y 的读数数组 y 升序排序。
- 遍历传感器 X 的每个读数 xi,根据不同情况累加合格配对个数:
- 若 K=0,任意非负乘积均 ≥0,所有 m 个 yj 都合格,贡献 m。
- 若 K>0 且 xi=0,乘积必为 0<K,无合格配对,跳过。
- 否则(xi>0),需要 yj≥⌈K/xi⌉。计算阈值
need = (K + x_i - 1) // x_i(向上取整)。在排序后的 y 中用二分查找找到第一个 >= need 的位置 pos,则后缀 y[pos…m−1] 全部合格,贡献 m−pos。