求助一道站外题
  • 板块学术版
  • 楼主syf159
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/11/12 11:59
  • 上次更新2023/11/12 14:20:24
查看原帖
求助一道站外题
840762
syf159楼主2023/11/12 11:59

第1题 蓝牙连接 n个人排队签到,队伍成一条直线,签到处位置为0,第i个人与签到处的距离是pi。排队是一件无聊的事情,所以他们可以通过手机蓝牙与附近的人连接聊天,蓝牙信号的有效距离是有限的,每个人只能与他距离不超过d的人进行蓝牙连接,这样这两个人就可以聊天了。已知每个人的位置和蓝牙的有效距离d,请你编程算出有多少组可以相互聊天的人。

输入格式 第1行一个整数n。(2≤n≤1000000)

第2行一个整数d。(0≤d≤1000000)

接下来有n行,每行有一个整数pi(0≤pi≤1 000 00000),表示每一个人与签到处的距离。

输出格式 一个整数,表示队伍中有多少组可以相互聊天的人。

输入/输出例子1 输入:

5 6 1 3 5 11 34

输出:

4

样例解释 样例说明:队伍中1和5,1和3,5和11,3和5一共4组人可以相互聊天。

【数据范围】

对于100%的数据,1≤n≤1000000。

本蒟蒻的错误代码:

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000005],m,sum;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1; i<n-1; i++)
    {
        int L=i,R=n,mid;
    	while(L+1<R)
    	{
    		mid=(L+R)/2;
    		if(a[mid]-a[i]>m) R=mid;
    		else L=mid+1;
		}
        int ans=n-i-(n-L+1);
		sum+=ans;
	}
    if(a[n]-a[n-1]<=m) sum++;
    cout<<endl<<sum;
    
    return 0;
}
2023/11/12 11:59
加载中...