贪心 : 首先尽可能找到 R 的最大值
然后找连通块数量即可
#include <bits/stdc++.h>
using namespace::std;
#define x first
#define y second
using PII = pair<int,int>;
const int N = 1e5 + 7;
int n,m,a,b,c;
PII w[N];
void readn() {
cin >> n;
for(int i = 0;i < n;i ++) {
cin >> w[i].x >> w[i].y;
}
sort(w,w + n);
int R = 1e9;
for(int i = 0;i < n - 1;i ++) {
if(w[i].y ^ w[i + 1].y) R = min(R,w[i + 1].x - w[i].x - 1);// 找到最小的 R
}
int res = 0;
for(int i = 0;i < n;i ++) {
if(w[i].y == 1) {
res ++;
i ++;
while(i < n && w[i].x - w[i - 1].x <= R) {
i ++;
}
i --;
}
}
cout<<res<<endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
readn();
return 0;
}
想问一下,不是要找到最大的R吗,为什么设置R=1e9呢?这样的话找到的不是最小R吗?
因为这里说的 R 是能满足要求的最大的 R 。 而我们需要找到 相邻的 有病 和 健康的牛 距离的 最小值 , 不妨设为 d , 那么 R < d 都是满足的 (一旦 R >= d 那么一定会存在一只健康的牛被生病的牛给感染) , 所以我们要找到最大的 R 等价于取 min(R,x - y) x,y 为健康和生病的牛的间隔距离
明白了,谢谢大佬!
https://www.acwing.com/solution/content/92394/
这篇详细的题解希望能够帮助大家!
%%%,原来生病牛和没病牛的最小距离就是要求的距离,所以可以不用二分,太强了大佬
哈哈哈哈哈,谢谢表扬 😀