上海计算机学会2022年9月月赛C++乙组T1区间交集（二）
发布时间
阅读量：
阅读量
区间交集（二）
内存限制: 256 Mb 时间限制: 1000 ms
题目描述
给定 n 个数轴上的闭区间，请统计有多少对区间的交集不是空集。
输入格式
第一行：一个整数 n；
接下来 n 行：每行两个整数 ai 与 bi，表示一个闭区间的左端点与右端点。
输出格式
单个整数：表示有多少对区间的交集不是空集。
数据范围
- 对于 30% 的数据，1≤n≤5,000；
- 对于 60% 的数据，1≤n≤20,000；
- 对于 100% 的数据，1≤n≤300,000；
- 1≤ai≤bi≤1,000,000；
样例数据
输入:
3
1 10
1 4
5 12
输出:
2输入:
2
1 2
2 3
输出:
1
说明:
两个闭区间的交可能只有一个数字，在这种情况下，也是符合非空要求的。输入:
5
1 10
3 4
6 8
2 9
7 7输出:
8
解析：二分法，详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans=0;
struct node{
int l;
int r;
} a[300005];
bool cmp(struct node a,struct node b){
return a.l<b.l;//按起点从小到大排序
}
int main(){
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i].l>>a[i].r;
}
sort(a+1,a+n+1,cmp);//排序
for (int i=1;i<=n-1;i++){//枚举每个区间
int lp=i,rp=n;//二分法求它后边第一个跟它不相交的
while (lp<rp){
int mp=(lp+rp+1)/2;
if ( a[i].r<a[mp].l){
rp=mp-1;
}else {
lp=mp;
}
}
ans+=rp-i;//增加数量
}
cout<<ans;
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~