AcWing 1660. 社交距离 II
原题链接
简单
作者:
不幸到吃土
,
2025-01-16 00:48:21
,
所有人可见
,
阅读 2
//先根据感染情况求出允许的最大感染半径,再根据感染半径逐个枚举奶牛的感染区间:区间内"两牛距离 < 感染半径" ,区间外"两牛距离 > 感染半径"
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 1010 , INF = 1e9;
PII cows[N];
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++){
cin >> cows[i].x >> cows[i].y;
}
sort(cows,cows+n);
int r = INF;
for(int i=1;i<n;i++){
if(cows[i].y != cows[i-1].y){ //若当前枚举的牛感染状态与前一头牛不相同,则计算与前一头牛的距离半径
r = min(r,cows[i].x - cows[i-1].x);
}
}
r--; //"感染半径"至少比"未感染距离"小1
int res = 0;
for(int i=0,j=0;i<n;i++){
if(cows[i].y){ //若当前牛被感染:遍历整个感染区间
j = i;
while(j<n && (cows[j+1].x - cows[j].x)<=r && cows[j+1].y)
j++;
res++;
i = j;
}
}
cout << res << endl;
return 0;
}