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

奶牛的耳语

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

【题目描述】

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

    相关文章

    【题解】BFS、DFS——走迷宫问题

    【题目描述】给定一个 n×m的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。最初,有一个人位于左上角 (1,...

    【题解】分糖果

    【题目描述】小A在生日这天收到了哥哥送来的一盒糖果,这盒糖果共有M个,小A要把这盒糖果放到N个盘子中(允许有盘子不放),请问,有多少种不同的放法?请注意:数值相同,顺序不同,我们视为是相同的放法,比如...

    【题解】摘花生问题

    【题解】摘花生问题

    【题目描述】Hello Kitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过...

    【题解】滚动的榜单

    【题目描述】某比赛的成绩,是依次出现的,而每个选手的成绩依次公布的时候,榜单都会刷新一遍,就能看到该选手在当前榜单加入时,所在的名次。下面给出了榜单选手的成绩,这里想知道,对于某个选手,求该选手在加入...

    【题解】解密

    【题解】解密

    【题目描述】给定一个正整数k,有k次询问,每次给定三个正整数ni,ei,di,求两个正整数pi,qi。使ni=pi *  qi,  ei * di =(pi -1) *(qi-1)...

    【题解】Power Strings

    【题目描述】给定若干个长度 ≤106 的字符串,询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如:ababab 则最多有 3 个 ab 连接而成。【输入描述】输入若干行,每行有一...