Codeforces 702C Cellular Network(二分)

时间：2021-09-19 17:48:05

题目链接：http://codeforces.com/problemset/problem/702/C

题意:

　　在数轴上有N个城市和M个信号塔，给你这N个城市以及M个塔在数轴上的位置，求M个塔可以覆盖N个城市的最小半径r。

思路:

　　刚开始想的是，对半径进行二分，但是考虑到每次对半径进行二分后，要判断这M个塔是否已经可以覆盖N个城市，判断这里找不到时间复杂度比较好的写法。后面想了想，对于每个城市，找到距离其最近的塔，计算出距离，在这N个距离中取最大的距离，就是最后要找的最小半径r了，这里同样利用二分来找距离城市最进的塔，二分的时候找到距离城市右边最近的塔，然后和城市左边第一个塔和城市的距离做判断，取较小的，就是距离城市最近的塔到城市的距离了。

代码：

 #include <iostream>

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <stack>

 #include <queue>

 #include <vector>

 #include <algorithm>

 #include <string>

 #define mearv(a, b) memset(a, b, sizeof(a))

 #define mestrc(a, b, c) memset(&(a), b, sizeof(c))

 typedef long long LL;

 using namespace std;

 const int MAXN = ;

 const LL INF = 1e15;

 int main() {

     LL a[MAXN + ] = {}, b[MAXN + ] = {};

     LL n, m;

     scanf("%I64d%I64d", &n, &m);

     for(int i = ; i < n; i++) scanf("%I64d", &a[i]);

     for(int i = ; i < m; i++) scanf("%I64d", &b[i]);

     b[m] = INF;

     LL ans = -;

     for(int i = ; i < n; i++){

         int lo = , hi = m;

         while(lo <= hi){//对塔进行二分，找到城市右边距离城市最进的塔。

             int mid = (lo + hi) >> ;

             if(a[i] <= b[mid]) hi = mid - ;

             else lo = mid + ;

         }

         int minn = lo;

         if(lo >  && (b[lo] - a[i] > a[i] - b[lo - ]) ) minn = lo - ;//和城市左边第一个塔进行比较

         ans = max(ans, abs(b[minn] - a[i]));//每次结果取最大值

     }

     printf("%I64d\n", ans);

     return ;

 }

相关文章