奶牛的耳语

【题目描述】

在你的养牛场，所有的奶牛都养在一排呈直线的牛栏中。一共有 n头奶牛，其中第 ii头牛在直线上所处的位置可以用一个整数坐标 pi(0<pi<10^8)来表示。在无聊的日子里，奶牛们常常在自己的牛栏里与其它奶牛交流一些八卦新闻。每头奶牛发出的声音响度是一样的，而由于声波的能量衰减，某头奶牛发出的声音只能被与它距离不超过 d(0≤d≤10^4) 的奶牛所听到，这样这对奶牛就称为可以相互交流的。现在给出所有奶牛的位置和声音所能传播的最远距离 d ，请你编个程序来计算你的养牛场里究竟有多少对可以相互交流的奶牛。

【输入描述】

第一行包含两个整数 n,d。
第二行包含 n个整数，每个整数都是一个坐标 pi，描述一头奶牛在直线上的位置。

【输出描述】

一个数，表示养牛场中可以相互交流奶牛的对数。

【样例输入】

5 10
10 12 16 37 40

【样例输出】

4

【数据规模】

对于 40% 的数据，1≤n≤10^3。
对于 100% 的数据，1≤n≤10^6。

---

【题目分析】

(1)因为牛都在一条直线上，可以通过排序达到剪枝的目的
(2)双重for循环去遍历所有的牛，如果不能交流就转入下一头，否则计数器加1
(3)输出计数器

---

#include<bits/stdc++.h>
using namespace std;
int a[1000001],n,f,i,j,k;
int main() {
	cin>>n>>f; //牛的数量和范围 
	for(i=1; i<=n; ++i)
		cin>>a[i];
	k=0;
	sort(a+1,a+(n+1));
	for(i=1; i<n; ++i)
		for(j=i+1; j<=n; ++j) {
			if(a[j]-a[i]>f) //双重循环遍历每一头牛 
				break;
			++k;
		}
	cout<<k;
	return 0;
}

---

返回目录:题解目录

---