AcWing 1660. 社交距离 II
原题链接
简单
作者:
向南_9
,
2022-02-16 16:17:41
,
所有人可见
,
阅读 237
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 1000010;
PII q[N];
int n, m = 0, s = N;
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> q[i].first >> q[i].second;
}
sort(q + 1, q + n + 1);
// 算出传播距离
for(int i = 2; i <= n; i ++)
{
if(q[i].second != q[i - 1].second) s = min(q[i].first - q[i - 1].first - 1, s);
}
for(int i = 1; i <= n; i ++)
{
if(q[i].second == 1)
{ //两点距离小于传播距离就直接改变
while(q[i + 1].second == 1 && (q[i + 1].first - q[i].first) <= s)
{
q[i + 1].second = 0;
i ++;
}
m ++;//统计改变后有多少感染源
}
}
cout << m << endl;
return 0;
}