题解：P9953 [USACO20OPEN] Social Distancing II B

解决思路：

根据奶牛的位置对数组进行排序。计算相邻健康奶牛和感染奶牛之间的最小距离。这个距离值减一用来估计感染传播的半径。（确保了感染奶牛之间的距离在当前半径下不会导致传播给其他健康奶牛。）

遍历排序后的奶牛列表，找到每一段连续感染奶牛的区域，并计算这些区域中可能需要的初始感染奶牛的数量。对于每一段连续感染奶牛，检查其能覆盖的区域，并增加初始感染奶牛的计数。

代码：

#include<bits/stdc++.h>
using namespace std;
struct cow{
	int x;
	bool h;
}a[1010];
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].x>>a[i].h;
	sort(a+1,a+n+1,[](const cow&a,const cow&b){return a.x<b.x;});
	int mr=INT_MAX;
	for(int i=1;i<n;i++)
		if(a[i].h!=a[i+1].h) mr=min(mr,a[i+1].x-a[i].x);
	mr--;
	int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i].h){
			++i;
			while(i<=n&&a[i].h&&a[i].x-a[i-1].x<=mr)
				++i;
			++ans;
			--i;
		}
	}
	cout<<ans;
}