CodeForce-702C Cellular Network(查找)

2021-07-04 12:13

阅读：481

标签：net str logs 查找最小 http long names put

Cellular Network

CodeForces - 702C

给定 n （城市数量）和 m （灯塔数量）；

给定 a1~an 城市坐标；

给定 b1~bm 灯塔坐标；

求出灯塔照亮的最小半径 r ，使得所有城市都能被照亮。

Input

3 2
-2 2 4
-3 0

Output

Input

5 3
1 5 10 14 17
4 11 15

Output

题解：

首先对于每个城市 a[ i ]，找到离它最近的左右两个灯塔 b [ x ] , b [ x-1 ]（只有最左或最右灯塔时特判），然后比较这两个灯塔与该城市的距离，取最小值 F [ i ] 。

对于所有的城市，要求出灯塔最小半径，要在 F [ 1 ] ~ F [ n ] 中求最大值。

#include
#include
#include
#include
#includestring>
using namespace std;

typedef long long ll;
const int N=1e5+50;
ll a[N];
ll b[N];
int n,m;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i)
        scanf("%lld",&a[i]);
    for(int i=0;i)
        scanf("%lld",&b[i]);
    ll ans=0;
    for(int i=0;i)
    {
        int x=lower_bound(b,b+m,a[i])-b;
        ll temp;
        if(x==0)//只有最左边灯塔
            temp=abs(a[i]-b[0]);
        else if(x==m)//只有最右边灯塔
            temp=abs(a[i]-b[m-1]);
        else //左右灯塔取最近之一
            temp=min(abs(a[i]-b[x]),abs(a[i]-b[x-1]));
        ans=max(ans,temp);//在各个城市与灯塔的距离中保留最大值比较出 r
    }
    coutendl;
    return 0;
}

CodeForce-702C Cellular Network(查找)

标签：net str logs 查找最小 http long names put

原文地址：http://www.cnblogs.com/YingZhixin/p/7109651.html

上一篇：jQuery笔记（一）jQuery选择器

下一篇：Internet explorer 已停止工作

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：CodeForce-702C Cellular Network(查找)
文章链接：http://soscw.com/essay/101728.html

亲，登录后才可以留言！

CodeForce-702C Cellular Network(查找)

Cellular Network

评论

热门文章

推荐文章

最新文章

置顶文章