Codeforces 702C Cellular Network

题目：这里

题意：一条数轴上，有n个城市和m个塔，分别给出城市的位置和塔的位置，每个塔有个覆盖范围，问能将所有城市都覆盖的塔的最小范围是多少，一个城市只要被至少一个塔

覆盖就行。

可以利用贪心的思想模拟一下，注意一下细节就行，也可以二分。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<map>
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 const int M = 1e5 + 10;
10 int a[M],b[M];
11 ll max(ll x,ll y){return x>y?x:y;}
12 
13 int main()
14 {
15     int n,m;
16     scanf("%d%d",&n,&m);
17     for (int i=1 ; i<=n ; i++) scanf("%d",&a[i]);
18     for (int i=1 ; i<=m ; i++) scanf("%d",&b[i]);
19     if (a[1]>=b[m])
20     {
21         printf("%I64d
",(ll)(a[n]-b[m]));
22         return 0;
23     }
24     if (b[1]>=a[n])
25     {
26         printf("%I64d
",(ll)(b[1]-a[1]));
27         return 0;
28     }
29     int j=1;ll ans=0;
30     for (int i=1 ; ; i++)
31     {
32          bool flag=false;
33          if (i>m) i=m;
34          while (i!=1&&abs(a[j]-b[i])>=abs(a[j]-b[i-1])&&j<=n)
35             j++,flag=true;
36          if (flag) ans=max(ans,abs(a[j-1]-b[i-1]));
37          if (j==n+1) break;
38          ll dis=abs(b[i]-a[j]);
39          while (abs(b[i]-a[j])<=dis&&i<=m)
40             dis=abs(b[i]-a[j]),i++;
41          i--;
42          while (abs(a[j]-b[i])<=dis&&j<=n)
43             j++;
44          ans=max(ans,dis);
45          //cout<<ans<<endl;
46          if (j==n+1) break;
47     }
48     printf("%I64d
",ans);
49     return 0;
50 }

二分

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<map>
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 const int M = 1e5 + 10;
10 ll a[M],b[M],n,m;
11 ll max(ll x,ll y){return x>y?x:y;}
12 
13 bool judge(ll x)
14 {
15     int j=1;
16     for (int i=1 ; i<=m ; i++)
17     {
18         while (a[j]>=b[i]-x&&a[j]<=b[i]+x&&j<=n)
19             j++;
20         if (j==n+1) return true;
21     }
22     return false;
23 }
24 
25 ll sreach ()
26 {
27     ll l=0,r=3e9,ans=0;
28     while (l<=r)
29     {
30         ll mid=(l+r)/2;
31         if (judge(mid)) ans=mid,r=mid-1;
32         else l=mid+1;
33     }
34     return ans;
35 }
36 
37 int main()
38 {
39     scanf("%d%d",&n,&m);
40     for (int i=1 ; i<=n ; i++) scanf("%I64d",&a[i]);
41     for (int i=1 ; i<=m ; i++) scanf("%I64d",&b[i]);
42     if (a[1]>=b[m])
43     {
44         printf("%I64d
",(ll)(a[n]-b[m]));
45         return 0;
46     }
47     if (b[1]>=a[n])
48     {
49         printf("%I64d
",(ll)(b[1]-a[1]));
50         return 0;
51     }
52 
53     printf("%I64d
",sreach());
54     return 0;
55 }