2906 - 【入门】相互认识
时间限制 : 1 秒
内存限制 : 128 MB
在某国,有 n 户渔民住在海岸线上,整齐的排列成一条直线。每个渔民的房子我们用一个坐标 p_i 来表示,每个渔民的活动半径为 d。也就是说两个距离小于等于 d 的房子,这两户渔民相互认识。
那么在某国,有多少对渔民相互认识?
输入
第一行输入两个整数 n\ (1 \le n \le 10^5),d\ (1 \le d \le 10^4),两数之间以一个空格分隔。
第二行输入 n 个整数 p_i\ (1 \le p_i \le 10^{8}),表示每个渔民房子的坐标(存在坐标相同的 p_i),相邻两数之间以一个空格分隔。
输出
输出一个整数,表示有多少对渔民相互认识。
样例
输入
5 10 10 12 16 37 40
输出
4
提示
直接两两比较每个渔民之间距离,时间复杂度为 \mathcal{O}(n^2),肯定过不了本题。
排序后,对每个渔民 i,统计他右边有多少户渔民和他距离小于等于 d,代码中的 pos 表示右边第一个距离 >d 的位置。
时间复杂度 \mathcal{O}(nlogn)。