贪心 + 双指针
只要推出每一个中间感染源的牛都可以被替换成他所能感染的最左边的牛感染而来就可以双指针,一个find函数来找出感染范围然后双指针就可以
#include <iostream>
#include <algorithm>
#include <cstring>
#define fs first
#define sc second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
PII a[N];
int n;
int find()
{
int r = 2e9;
for(int i = 0; i < n; i ++)
{
if(a[i].sc != a[i + 1].sc) r = min(r, a[i + 1].fs - a[i].fs);
}
return r;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
{
int x, b;
scanf("%d%d", &x, &b);
a[i] = {x, b};
}
a[n] = {2e9, 0};
sort(a, a + n + 1);
int r = find();
//cout << r << endl;
int res = 0;
for(int i = 0; i < n; i ++)
{
if(a[i].sc == 1)
{
int j = i;
while(a[j + 1].fs - a[j].fs < r && j + 1 < n) j ++;
res ++;
i = j;
}
}
cout << res << endl;
return 0;
}