首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#12882

能量节点 题目描述 数轴上分布着 n 个能量节点,第 i 个节点的坐标为 x i 。 当两个节点的距离小于等于 d 时,会产生能量共鸣。 求一共有多少组节点会发…

能量节点

题目描述

数轴上分布着 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。

限制

时间限制:1000ms

内存限制:256MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;algorithm&gt; int main() {     int n, d;     std::cin &gt;&gt; n &gt;&gt; d;     int a[100005];     for(int i = 1;i &lt;= n; ++i)         std::cin &gt;&gt; a[i];     std::sort(a + 1, a + n + 1);          long long pair = 0;     for(int i = 1, j = 1; i &lt;= n; ++i)     {         while(a[j] - a[i] &lt;= d &amp;&amp; j &lt;= n)             j++;         pair += j - i - 1;     }     std::cout &lt;&lt; pair; }</pre>
这道题暂未补解析。