Educational Codeforces Round 15 Cellular Network

时间：2021-05-23 17:48:01

Cellular Network

题意：

给n个城市，m个加油站，要让m个加油站都覆盖n个城市，求最小的加油范围r是多少。

题解：

枚举每个城市，二分查找最近的加油站，每次更新答案即可，注意二分的时候不要越界oil数组，上下界都不要越。还有，int坑死人，以后绝对全用long long！！！

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF=0x3f3f3f3f;

const ll LINF=0x3f3f3f3f3f3f3f3f;

#define PU puts("");

#define PI(A) cout<<A<<endl

#define SI(N) cin>>N

#define SII(N,M) cin>>N>>M

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

#define dbg(x) cout <<#x<<" = "<<x<<endl

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS= 1e-9 ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN= 100000 + 9 ;

ll city[MAXN],oil[MAXN];

ll N,M;

int main()

{

    iostream::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    while(SII(N,M))

    {

        rep(i,N)SI(city[i]);

        rep(i,M)SI(oil[i]);

        ll ans=0;

        rep(i,N)

        {

            ll t=lower_bound(oil,oil+M,city[i])-oil;

            ll d=LINF;

            if (t<M)

            d=abs(oil[t]-city[i]);

            ll d2=LINF;

            if (t-1>=0)

            d2=abs(oil[t-1]-city[i]);

            ans=max(ans,min(d,d2));

        }

        PI(ans);

    }

    return 0;

}

相关文章