AcWing 1660. 社交距离 II(排序 + 线性扫描,29 行,15 ms)
原题链接
简单
作者:
ᔠዂϤ
,
2022-02-15 23:03:17
,
所有人可见
,
阅读 204
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005, inf = 1e8;
typedef pair<int, bool> pib;
#define x first
#define y second
pib cow[N];
int n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d%d", &cow[i].x, &cow[i].y);
sort(cow, cow + n);
int r = inf;
for (int i = 1; i < n; i++)
if (cow[i].y ^ cow[i - 1].y)
r = min(r, cow[i].x - cow[i - 1].x);
int res = 0, tag = cow[0].y;
for (int i = 1; i < n; tag |= cow[i++].y)
if (cow[i].x - cow[i - 1].x >= r)
res += tag, tag = 0;
printf("%d", res + tag);
}