A17460. 能量节点
填空题
困难
知识点
题目描述
能量节点
题目描述
数轴上分布着 n 个能量节点，第 i 个节点的坐标为 xi 。
当两个节点的距离小于等于 d 时，会产生能量共鸣。
求一共有多少组节点会发生能量共鸣。
输入格式
第一行，两个整数表示 n 与 d。
第二行，n 个整数，表示 x1,x2,…,xn 。
输出格式
单个整数：表示有多少对点可以会产生能量共鸣。
输入样例
4 25
30 40 10 20输出样例
5说明提示
1≤n≤100,000，
1≤d≤1,000,000,000，
1≤xi≤1,000,000,000。
参考答案
#include<iostream>
#include<algorithm>
int main()
{
int n, d;
std::cin >> n >> d;
int a[100005];
for(int i = 1;i <= n; ++i)
std::cin >> a[i];
std::sort(a + 1, a + n + 1);
long long pair = 0;
for(int i = 1, j = 1; i <= n; ++i)
{
while(a[j] - a[i] <= d && j <= n)
j++;
pair += j - i - 1;
}
std::cout << pair;
}
上一题
下一题