Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

Comet OJ - 2019国庆欢乐赛 C题 两排房子

大头冲锋车丶 2019-11-17 21:52:00 阅读数:18 评论数:0 点赞数:0 收藏数:0

###题目链接###

 

题目大意:这里有横着的两排房子,给你每个房子的左端点和右端点。若两排房子中分别有两个房子 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=;i<=n;i++){
 scanf("%d%d",&a[i].l,&a[i].r);
 }
 sort(a+,a+n+,cmp1);
 int A,B;
 for(int i=;i<=m;i++){
 scanf("%d%d",&A,&B);
 int st=lower_bound(a+,a+n+,Node(,A),cmp2)-a;
 int en=upper_bound(a+,a+n+,Node(B,),cmp1)-a-;
 ans+=1ll*(en-st)+1ll;
 }
 printf("%lld\n",ans );
}

 

版权声明
本文为[大头冲锋车丶]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/Absofuckinglutely/p/11878538.html