AcWing 1660. 社交距离 II
原题链接
简单
作者:
885377
,
2022-02-15 21:31:13
,
所有人可见
,
阅读 331
#include<iostream>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int N=1010;
typedef pair<int,int>PII;
PII a[N];
int main()
{
int n;
scanf("%d",&n);
int distance;
for(int i=0;i<n;i++)
{
scanf("%d %d",&a[i].x,&a[i].y);
}
sort(a,a+n);//排序
for(int i=0;i<n;i++) //找到R
{
if(!a[i].y)
{
if(!i&&a[i+1].y)distance=min(distance,a[i+1].x-a[i].x);
if(i&&a[i-1].y)distance=min(distance,a[i].x-a[i-1].x);
if(i&&a[i+1].y)distance=min(distance,a[i+1].x-a[i].x);
}
}
int cnt=0;
for(int i=0;i<n;i++)//分情况找到不同的集合 可以看作昨天的每日一题 求不同子段的数量
{
if(!i&&a[i].y)cnt++; //第一个为1
if(i&&!a[i-1].y&&a[i].y)cnt++; //前者和现在 一个为0 一个为1
if(i&&a[i-1].y&&a[i].y&&a[i].x-a[i-1].x>=distance)cnt++;//前者 和现在都为1但距离>=R
}
cout<<cnt;
}