诸城网站建设诸城,免费网站建设免费咨询,网站如何做地推,wordpress如何加联盟广告位题目描述
这是上海计算机学会竞赛 P 243 P243 P243#xff1a;5G通讯#xff08; 2020 2020 2020年 9 9 9月月赛 乙组 T 2 T2 T2#xff09;标签#xff1a;二分查找题意#xff1a;给定 n n n个点#xff0c;第 i i i个点的坐标为 x i x_i xi。给定限制 d d d#…题目描述
这是上海计算机学会竞赛 P 243 P243 P2435G通讯 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 1n10^5,1x_i,d10^9 1n105,1xi,d109
解决方案
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 ai−d的数。 a i − a j d a_i-a_jd ai−ajd转换成 a i − d a j a_i-da_j ai−daj那这一部分是不是可以用二分查找去找一下。然后简单思考一下最极端的情况是不是有 n ∗ ( n − 1 ) / 2 n*(n-1)/2 n∗(n−1)/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;
}
