AcWing 1660. 社交距离 II
原题链接
简单
作者:
Kyshren
,
2022-02-15 23:05:43
,
所有人可见
,
阅读 213
贪心求最短的半径,然后通过半径求在半径距离内连续的奶牛
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1010,INF = 1e6 + 10;
int n;
PII a[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) scanf("%d%d", &a[i].x, &a[i].y);
sort(a, a + n);
int len = INF;
for(int i = 0; i < n; i ++)
if(a[i].y == 0)
{
int j = i;
while(a[j].y == 0 && j >= 0) j --;
if(j >= 0 && a[j].y == 1) len = min(len,a[i].x - a[j].x - 1);
j = i;
while(a[j].y == 0 && j < n) j ++;
if(j < n && a[j].y == 1) len = min(len,a[j].x - a[i].x - 1);
}
int res = 0;
for(int i = 0; i < n; i ++)
{
if(a[i].y == 1)
{
int j = i;
res ++;
while(a[j + 1].x - a[j].x <= len && j < n) j ++;
i = j;
}
}
cout << res << endl;
return 0;
}