AcWing 1660. 社交距离 II
原题链接
简单
作者:
静静在Coding
,
2022-03-26 17:19:30
,
所有人可见
,
阅读 175
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
PII q[N];
int main()
{
int n;
cin>>n;
for(int i = 1;i <= n;i++) cin>>q[i].first>>q[i].second;
sort(q+1,q + n + 1);
int R = 1e8;
for(int i = 1;i < n;i++){
if(q[i].second != q[i + 1].second) R = min(R,q[i + 1].first - q[i].first);
}
R = R - 1;
//cout<<R<<endl;
int res = 0;
for(int i = 1;i <= n;i++){
if(q[i].second){
int j = i + 1;
while(q[j].first - q[j - 1].first <= R && j <= n) j++; //没生病的奶牛一定比R大
res++;
i = j - 1;
}
}
cout<<res;
return 0;
}