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

奶牛的耳语

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

【题目描述】

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

【题解】求逆序对个数

【题目描述】有一实数序列A[1]、A[2] 、A[3] 、……A[n-1] 、A[n] (n<10000),若i<j,并且A[i]>A[j],则称A[i]与A[j]构成了一个逆序对,...

【题解】导弹拦截

【题目描述】某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导...

【题解】发工资

【题目描述】作为程序猿,最盼望的日子就是每月的9号了,因为这一天是发工资的日子,养家糊口就靠它了,呵呵但是对于公司财务处的工作人员来说,这一天则是很忙碌的一天,财务处的小李最近就在考虑一个问题:如果每...

【题解】阶乘的末尾

【题目描述】n的阶乘定义为n!=1*2*3*……*n  如3!=6   n!通常最后会有很多0,如5!=120  最后有一个0,现在统计n!去除末尾的0后,最后k位是多少...

【题解】均分蛋糕

【题目描述】小明今天生日,他有n块蛋糕要分给朋友们吃,这n块蛋糕(编号为1到n)的重量分别为a1, a2, …, an。小明想分给每个朋友至少重量为k的蛋糕。小明的朋友们已经排好队准备领蛋糕,对于每个...