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

奶牛的耳语

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

【题目描述】

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

    相关文章

    【题解】将钱分给最多的儿童

    【题目描述】给你一个整数 money ,表示你总共有的钱数(单位为美元)和另一个整数 children ,表示你要将钱分配给多少个儿童。你需要按照如下规则分配:...

    【题解】黑白棋子移动

    【题目描述】有2n个棋子(n≥4)排成一行,开始位置为白子全部在左边,黑子全部在右边,如下图为n=5的情形:○○○○○●●●●●移动棋子的规则是:每次必须同时移动相邻的两个棋子,颜色不限,可以左移也可...

    【题解】区间数位个数

    区间数位个数(digit.cpp)【描述】给定整数n和整数k,求出1~n中所有数的每一位数字中,出现数字k的次数。【输入】第一行是两个个整数n和k【输出】一个整数表示答案。【样例输入输出】light....

    【题解】2001-T1 数的计数

    【题目描述】我们要求找出具有下列性质数的个数(包含输入的自然数nn):先输入一个自然数n(n≤1000)n(n≤1000),然后对此自然数按照如下方法进行处理:1.不作任何处理;2.在它的左边加上一个...

    数的拆分(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...

    2的幂次方表示

    【题目描述】任何一个正整数都可以用2的幂次方表示。例如:137=27+23+20同时约定方次用括号来表示,即ab可表示为a(b)。由此可知,137可表示为:2(7)+2(3)+2(0)进一步:7=22...