算法1
(双指针、贪心) $O(nlog(n))$
解题思路
得到没感染之前得病牛的数量,我们需要确定一个最大的$R$来解除当前状态下尽可能数量多的被传染的牛,对于需要确定的$R$,我们按顺序找出每一段没被感染牛群的两侧端点的索引$L,R$,分别记录$L$与$L-1$(如果有效,则处于该索引位置的牛必定是病牛),间的距离$R1$,同理记录右侧的值为$R2$,对于该段健康牛群,感染距离必然会小于min(R1, R2)
(贪心),否则左右端点处的某头牛就会被感染成病牛。具体实现中,由于健康牛群的内部对$R$没有影响,我们不考虑内部,所以我们可以正反两次遍历并借助双指针分别找到感染牛群的最右侧(对应到健康牛群的左侧端点)和最左侧(对应到健康牛群的右侧端点)。
时间复杂度
由于我们需要按位置大小有序来遍历,所以需要进行排序$O(nlog(n))$,找$R$的时间复杂度是$O(n)$,最后确定病牛是否是被传染的,即最开始是健康的牛,我们也只需遍历一遍,所以最后的时间复杂度为$O(nlog(n))$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
int n;
vector<PII> h;
int main()
{
cin >> n;
int cn = 0;
for(int i = 0; i < n; i ++)
{
int x, y;
scanf("%d%d", &x, &y);
h.push_back({x, y});
if(y == 1) cn ++;
}
sort(h.begin(), h.end());
int R = 0x3f3f3f3f;
for(int i = 0; i < n; i ++)
{
int j = i;
while(j < n && h[j].second == 1) j ++;
if(j == i) i = j;
else if(j != n) R = min(R, h[j].first - h[j - 1].first);
}
for(int i = n - 1; i >= 0; i --)
{
int j = i;
while(j >= 0 && h[j].second == 1) j --;
if(j == i) i = j;
else if(j != -1) R = min(R, h[j + 1].first - h[j].first);
}
int cnt = 0;
for(int i = 0; i < n; i ++)
{
if(h[i].second == 0) continue;
if(i + 1 < n && h[i].second == 1 && h[i + 1].second == 1)
{
if(h[i + 1].first - h[i].first < R) cnt ++;
}
}
cout << cn - cnt;
return 0;
}