【每日一题】YACS 243:5G通讯

2024-01-28 12:28
文章标签 每日 通讯 5g 243 yacs

本文主要是介绍【每日一题】YACS 243:5G通讯,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

这是上海计算机学会竞赛 P 243 P243 P243:5G通讯( 2020 2020 2020 9 9 9月月赛 乙组 T 2 T2 T2
标签:二分查找
题意:给定 n n n个点,第 i i i个点的坐标为 x i x_i xi。给定限制 d d d,如果两点距离不超过 d d d,那么它们可以直接通讯,统计可以有多少对点可以直接通讯。( 1 < = n < = 1 0 5 , 1 < = x i , d < = 1 0 9 1<=n<=10^5,1<=x_i,d<=10^9 1<=n<=105,1<=xi,d<=109

解决方案

80 分题解:很多同学直接暴力枚举第 i i i个点前有多少个点和它的坐标距离不超过 d d d,这个写法也不错,并且因为是枚举第 i i i个点前的,还可以避免重复的情况出现(即 ( a , b ) (a,b) (a,b) ( b , a ) (b,a) b,a的情况)。但是时间复杂度是 O ( n 2 ) O(n^2) O(n2),还是会超时。
80 分代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
ll n, d, a[100005];int main() {cin >> n >> d;for (int i = 1; i <= n; i++) cin >> a[i];// 排序 保证序列有序sort(a + 1, a + 1 + n);ll cnt = 0; // 直接通讯的点对数for (int i = 1; i <= n; i++) {for (int j = 1; j < i; j++) {if (a[i] - a[j] <= d) cnt++;}}cout << cnt;return 0;
}

题解:正解应该比较容易想到第二层 j j j循环能不能优化,想一想这层循环的逻辑其实就是想在第 i i i个数前找有多少个大于等于 a i − d a_i-d aid的数。( a i − a j < = d a_i-a_j<=d aiaj<=d转换成 a i − d < = a j a_i-d<=a_j aid<=aj),那这一部分是不是可以用二分查找去找一下。然后简单思考一下,最极端的情况是不是有 n ∗ ( n − 1 ) / 2 n*(n-1)/2 n(n1)/2个点对,会爆掉 i n t int int,得开 l o n g l o n g long\ long long long
代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
ll n, d, a[100005];int main() {cin >> n >> d;for (int i = 1; i <= n; i++) cin >> a[i];// 排序 保证序列有序sort(a + 1, a + 1 + n);ll cnt = 0; // 直接通讯的点对数for (int i = 1; i <= n; i++) {ll p = lower_bound(a + 1, a + 1 + n, a[i] - d) - a;cnt += i - p;}cout << cnt;return 0;
}

这篇关于【每日一题】YACS 243:5G通讯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/653626

相关文章

如何使用C#串口通讯实现数据的发送和接收

《如何使用C#串口通讯实现数据的发送和接收》本文详细介绍了如何使用C#实现基于串口通讯的数据发送和接收,通过SerialPort类,我们可以轻松实现串口通讯,并结合事件机制实现数据的传递和处理,感兴趣... 目录1. 概述2. 关键技术点2.1 SerialPort类2.2 异步接收数据2.3 数据解析2.

4G/5G全网通! FiberHome烽火5G CPE Air路由器拆机评测

《4G/5G全网通!FiberHome烽火5GCPEAir路由器拆机评测》烽火5GCPE已经使用一段时间了,很多朋友想要知道这款路由器怎么样?今天我们就来看看拆机测评... 我想大家都听说过、了解过5G。 5G是具有高速率、低时延和大连接特点的新一代宽带移动通信技术,5G通讯设施是实现人机物互联的网络基础设

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

Java Websocket实例【服务端与客户端实现全双工通讯】

Java Websocket实例【服务端与客户端实现全双工通讯】 现很多网站为了实现即时通讯,所用的技术都是轮询(polling)。轮询是在特定的的时间间隔(如每1秒),由浏览器对服务器发 出HTTP request,然后由服务器返回最新的数据给客服端的浏览器。这种传统的HTTP request 的模式带来很明显的缺点 – 浏 览器需要不断的向服务器发出请求,然而HTTP

每日一练7:简写单词(含链接)

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1(错误经验) #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣(LeetCode) 2. LCR 098. 不同路径 - 力扣(LeetCode) 3. 63. 不同路径 II - 力扣(LeetCode) 1. 91. 解码方法 - 力扣(LeetCode) //思路:动态规划。 cl

STM32 HAL CAN通讯 实操

1、简介 相比于串口通讯,对于刚接触CAN通讯的小白来说,CAN通讯相对复杂,看各种视频、帖子理论,总是一知半解。本次通过傻瓜式操作,先实现CAN通讯的交互,以提高小白的信心,也便于自己复习观看。本次以STM32CubeMX进行初始化配置,通过Keil 5软件进行软件设计,通过CAN盒实现进行数据的交互。该流程实际以STM32F0、F1、F3、F4、F7实测好用(理论上都适用),这三种型号单片机

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

每日一题——第八十一题

打印如下图案: #include<stdio.h>int main() {int i, j;char ch = 'A';for (i = 1; i < 5; i++, ch++){for (j = 0; j < 5 - i; j++){printf(" ");//控制空格输出}for (j = 1; j < 2 * i; j++)//条件j < 2 * i{printf("%c", ch