当前位置:首页 > 题解目录 > 正文内容

奶牛的耳语

亿万年的星光5年前 (2021-01-28)题解目录4998

【题目描述】

在你的养牛场,所有的奶牛都养在一排呈直线的牛栏中。一共有 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;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:
返回列表

上一篇:猴子吃桃

下一篇:数的拆分(1)

相关文章

线段

题目描述在一个数轴上有n条线段,现选取其中k条线段使得这k条线段两两没有重合部分,问最大的k为多少?输入格式第一行为一个正整数n,下面n行每行2个数字ai,bi,描述每条线段。输出格式输出文件仅包括1...

数的拆分(1)

【题目描述】任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和。例如:当n=7时7=1+1+1+1+1+1+1 7=1+1+1+1+1+2 7=1+1+1+1+3 7=1+1+1+2...

【题解】大整数加法

【题目描述】求两个不超过200位的非负整数的和。【输入】有两行,每行是一个不超过200位的非负整数,可能有多余的前导0。【输出】一行,即相加后的结果。结果里不能有多余的前导0,即如果结果是342,那么...

【题解】01串

【题目描述】Fans是个ACM程序设计迷。有时侯,他表现出很强烈的逆反心理,你往东,他往西,你往南,他偏往北。这一次,不知道又是谁惹着他了,好端端的一个个01串,到了他的手里,都变成10串了。请你编个...

【题解】增添战斗力

【题目描述】大战即将来临,杰洛特需要为自己增添战斗力,广袤的大陆有诸多豪杰,正好可以为杰洛特所用    杰洛特分别有两处地方n1,n2需要豪杰的战斗力    一...

【题解】前缀最大值

【题目描述】求一个数列的所有前缀最大值之和。即:给出长度为n的数列a[i],求出对于所有1<=i<=n,max(a[1],a[2],...,a[i])的和。比如,有数列:666 304 6...