题解：P17134 [KOI 2026 #1] 邻居

· · 题解

题解：P17134 [KOI 2026 #1] 邻居

题意

有 N 个人，分别在两所学校中，如果两个人之间是邻居，那么如果属于同一所学校时距离要小于 K_1，如果不属于同一所学校，则距离要小于 K_2。

对于题目来源、详细原题目描述 输入输出格式、样例、数据范围等信息，请返回 Problem。

思路

如果不知道下列用到的算法且目前会因此影响阅读，建议先查对应资料。

0x00 方法：枚举

做法：

枚举对于每一个人，判断其他所有人是否与这个人互为邻居，最终求出每一个人的邻居数量。

是否能过：

时间复杂度 O(N^2)，可以过题，但是还能优化。

0x01 方法：二分

做法： 实际上，可以首先记录每一所学校都有哪些人并按照编号排序（或者保证记录顺序是有序的）。

然后，对于每一个人（编号为 i），先找出这个人属于哪一所学校，然后，二分计算与这个人学校相同的人中编号 [i-X_1,i+X_1] 的人数与这个人学校相同的人中编号 [i-X_2,i+X_2] 的人数之和减一（因为不能算上自己）。 :::info[提示] 在求某一所学校中编号 [i,j] 的人的人数，可以计算编号不小于 i 的人数与编号不小于 j+1 的人数之差。 :::

是否能过：

时间复杂度 O(N\times \log(N))，可以过题。

其他

:::success[AC 记录] 我的 AC 记录。 ::: :::info[注明]

  1. 本题解所有未声明变量均与题目相同。 :::