题解：CF2223B Zhily and Barknights

ACehomoxue · 2026-05-07 17:58:18 · 题解

题目 link

博客园 link

先把期望转成计数，发现不好直接算考虑拆贡献。对于每一个 a_i 与 a_j 且 j < i，我们可以统计存在多少组 x 和 y 使得 a_i \times b_x < a_j \times b_y。a_i \times b_x < a_j \times b_y 不太好统计，转换成 \frac{a_j}{a_i} > \frac{b_x}{b_y}。我们发现题目中 n \le 2000，于是我们可以预处理所有的 \frac{a_j}{a_i} 和 \frac{b_x}{b_y}，分别放到一个数组里面然后排序，双指针找 \frac{a_j}{a_i} > \frac{b_x}{b_y} 的对数，然后就做完了，时间复杂度 O(n ^ 2 \log n)。需要注意的是不要用 double 否则有精度误差，应手写分数并且交叉相乘比大小。

code