找到最短不被感染的距离r,然后先让ans等于1,表示第一个出现的默认是感染源,因为只要有范围以内的连续感染,无论在那个位置都会感染到,我这没考虑全都不感染的情况,看样子也没有这种情况,毕竟不是哪里都有力扣的阴间空集。然后只要当前点被感染,并且和上个牛的距离大于等于r(等于是因为刚好不被感染,所以要算上),然后计算就行了
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
pair<int, int> c[1005];
int main()
{
int n;
cin>>n;
int a,b;
for (int i = 0; i < n; i ++ ){
cin>>a>>b;
c[i] = {a,b};
}
sort(c,c+n);
int r = 1e6+5;
for (int i = 1; i < n; i ++ ){
if(c[i].second != c[i-1].second) r = min(r, c[i].first - c[i-1].first);
}
int ans = 1;
for (int i = 1; i < n; i ++ ){
if(!c[i].second) continue;
if(c[i].first - c[i-1].first >= r) ans++;
}
cout<<ans<<endl;
return 0;
}
这里有个问题,就是答案的验证集里面,第一头出现的牛必定被感染的,也就是如果第一头牛是0,我这个代码是错误的,只需要改一下就行,ans=c[0].second,这样,第一头牛是1,刚好我们的答案初始值也是1,当第一头牛是0,我们的答案初始值刚好也取0
如果我们ans=1写死,c[i].first - c[i-1].first >= r这句话,当第一头牛是0,第二头牛是1,我们就吧第二头牛算两次了。答案就是错误的
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
pair<int, int> c[1005];
int main()
{
int n;
cin>>n;
int a,b;
for (int i = 0; i < n; i ++ ){
cin>>a>>b;
c[i] = {a,b};
}
sort(c,c+n);
int r = 1e6+5;
for (int i = 1; i < n; i ++ ){
if(c[i].second != c[i-1].second) r = min(r, c[i].first - c[i-1].first);
}
int ans = c[0].second;
for (int i = 1; i < n; i ++ ){
if(!c[i].second) continue;
if(c[i].first - c[i-1].first >= r) ans++;
}
cout<<ans<<endl;
return 0;
}