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

奶牛的耳语

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

【题目描述】

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

相关文章

【题解】切比雪夫距离

【题目描述】小C有一个平面!它发现了平面上的两个点,请你求出求它们之间的切比雪夫距离。切比雪夫距离定义为x与y方向坐标差的绝对值较大值。【输入描述】四个整数,a,b,c,d。坐标为(a,b)与(c,d...

【题解】泥泞路(2019青岛市程序设计竞赛)

【题目描述】大雨过后,从小A的农场到镇上的公路上有一些泥泞路段,为了方便出行,他决定将若干块长度为L的木板可以铺在这些泥泞路段上,问他至少需要多少块木板,才能将所有的泥泞路段覆盖住。【输入】第一行为正...

【题解】计算天数

【题目描述】以 年-月-日 的形式给定一个日期,计算给定的日期是当年第几天。注意闰年二月有29天。【输入描述】输入格式为 yyyy-mm-dd,其中yyyy 表...

【题解】Best Cow Fences

【题目描述】    给定一个长度为n的正整数序列A。求一个平均数最大的,长度不小于L的子序列。【输入描述】第一行,n和L;n个正整数,表示A。【输出描述】&nb...

【题解】建设病房

1.建设病房(build.cpp)【题目描述】2020年1月23日下午,武汉市建设局紧急召集中建三局等单位举行专题会议,要求参照2003年抗击非典期间北京小汤山医院模式,在武汉职工疗养院建设火神山医院...

【题解】分发饼干

【题目描述】假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;...