Comet OJ - 2019国庆欢乐赛 C题 两排房子
大头冲锋车丶 人气:4###题目链接###
题目大意:这里有横着的两排房子,给你每个房子的左端点和右端点。若两排房子中分别有两个房子 x y ,他们在横坐标上有重叠部分(端点重叠也算),则被称为 “对门” 关系。
问你总共有多少个 “对门” 关系。
分析:
显然题目要让你求的是,枚举第一排各个房子,然后找第二排有多少个房子区间与之有交集部分。
第一排: [ ]
第二排:[ ] [ ] [ ] [ ]
画一下可以看出:将第二排的房子以左端点从小到大排序后,对应找第一排某个房子的贡献,只需要找到第一排的这个房子的区间内,能括起来多少个房子即可。
由于只要有重叠就算,故假设第一排的某个房子的左右端点为 a b ,第二排的某个房子中,左右端点为 x y ,那么只要在第二排中二分:
1、找到第一个大于等于 a 的 y ,然后记下起点标号 st 。
2、找到最后一个小于等于 b 的 x ,然后记下终点标号 en。
故第一排这个房子所能提供的贡献为:en - st + 1 。
代码如下:
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; int n,m; ll ans; struct Node{ int l,r; Node(){}; Node(int _l,int _r){ l=_l,r=_r; } }a[400008]; bool cmp1(Node q,Node w){ return q.l<w.l; } bool cmp2(Node q,Node w){ return q.r<w.r; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d%d",&a[i].l,&a[i].r); } sort(a+1,a+n+1,cmp1); int A,B; for(int i=1;i<=m;i++){ scanf("%d%d",&A,&B); int st=lower_bound(a+1,a+n+1,Node(0,A),cmp2)-a; int en=upper_bound(a+1,a+n+1,Node(B,0),cmp1)-a-1; ans+=1ll*(en-st)+1ll; } printf("%lld\n",ans ); }
加载全部内容