社交距离II

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,ans=1e9,sum;
 4 struct node{
 5     int p,k,MIN;//位置，是否被感染，离最近的被感染的牛的距离，
 6     bool flag;//用来后面继承的
 7 }a[1010];
 8 bool cmp(node x,node y){return x.p<y.p;}
 9 int main()
10 {
11     freopen("socdist2.in","r",stdin);
12     freopen("socdist2.out","w",stdout);
13     scanf("%d",&n);
14     for(int i=1;i<=n;i++)
15     {
16         scanf("%d%d",&a[i].p,&a[i].k);
17         a[i].MIN=1e9;
18     }
19     sort(a+1,a+1+n,cmp);
20     for(int i=1;i<=n;i++)//找最小值的操作
21     {
22         for(int j=1;j<i;j++)
23         {
24             if(a[i].k)
25                 a[j].MIN=min(a[j].MIN,a[i].p-a[j].p);//如果当前是被感染的，那么前面的要继承
26                 
27             if(a[j].k)
28                 a[i].MIN=min(a[i].MIN,a[i].p-a[j].p);//如果前面的是被感染的，那么自己要继承
29         }
30     }
31     for(int i=1;i<=n;i++)
32         if(!a[i].k)ans=min(ans,a[i].MIN);//找R半径
33     ans--;
34     for(int i=1;i<=n;i++)
35     {
36         if(a[i].k)//如果被感染
37         {
38             for(int j=i-1;j>0;j--)//遍历
39             {
40                 if(a[i].p-a[j].p>ans)break;//超过半径退出
41                 if(a[j].flag)//如果之前的标记的就继承
42                 {
43                     a[i].flag=1;
44                     break;
45                 }
46                
47             }
48             if(!a[i].flag)a[i].flag=1,sum++;//否则就疾病开始传播之前已经得病的奶牛的最小数量++
49         }
50     }
51     cout<<sum<<endl;
52     return 0;
53 }