【第021题】题解代码分享：10点40还摁着亲闺女刷题：Cellular Network

小码匠

发布于 2023-12-13 10:54:51

1370

发布于 2023-12-13 10:54:51

文章被收录于专栏：小码匠和老码农小码匠和老码农

大家好，我是小码匠。

早晨跟妈妈吐槽老码农。晚上10点40还摁着亲闺女刷题，这老爸当的。。。

昨天到家本来就晚，都10点了，然后作业还没写完，我快速写完作业，又去洗澡，就10:40了。

随口问了句老码农，老码农尽然还问：有没有兴趣再刷一道题。

一听我就没好气，刷，我到11点就睡觉。。。

前置知识

二分查找

路漫漫其修远兮，吾将上下而求索

离自己的既定目标：

目标：300道
已完成：21道
待完成：279道

题目地址

https://www.luogu.com.cn/problem/CF702C

在直线上给出n个城市的位置(x坐标)和在同一直线上的m个蜂窝塔的位置(x坐标)。所有的塔都以同样的方式工作——它们为所有城市提供蜂窝网络，这些城市位于离塔不超过r的距离处才能被蜂窝网络覆盖。

你的任务是找出使得每个城市都能被蜂窝网络覆盖的最小r值，即每个城市在距离r的范围内至少有一个蜂窝塔。

如果r=0，则塔仅为其所在的位置提供蜂窝网络。一个塔可以为任意数量的城市提供蜂窝网络，但是所有这些城市都必须在距离塔不超过r的距离上。

输入格式

第一行包含两个正整数n和m，表示有n个城市与m个蜂窝塔。
第二行包含n个整数a[1],a[2]...a[n]，表示每个城市的位置(x坐标)
第三行包含m个整数b[1],b[2]...b[m]，表示每个蜂窝塔的位置(x坐标)

注意，允许多个城市或蜂窝塔位置相同。

输出格式

输出最小的r，使得每个城市都被蜂窝网络覆盖。

数据范围

1<=n,m<=10^5

-10^9<=a[i]<=10^9

-10^9<=b[j]<=10^9

输入输出样例

输入 #1复制

3 2
-2 2 4
-3 0

输出 #1复制

输入 #2复制

5 3
1 5 10 14 17
4 11 15

输出 #2复制

知识点

二分

题解

本题属于一眼二分，题解就不写了，看代码吧。

AC代码

#include <bits/stdc++.h>

using namespace std;

const int MAX_NUM = 1e5 + 5;
long long a[MAX_NUM], b[MAX_NUM];
int n, m;

bool check(long long len) {
    int l = 0;
    int i;
    int cnt = 1;
    for (i = 0; i < n && l < m; ++i) {
        while (abs(b[l] - a[i]) > len) {
            ++l;
            ++cnt;
        }
    }

    return cnt <= m;
}


void best_coder() {
    cin >> n >> m;
    for (int i = 0 ; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0 ; i < m; ++i) {
        cin >> b[i];
    }

    sort(a, a + n);
    sort(b, b + m);

    long long l = 0, r = LONG_LONG_MAX;
    while (l < r) {
        long long mid = l + r >> 1;
        if(check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    cout << r;
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

学习代码：二分算法

#include <bits/stdc++.h>
using namespace std;

// returns the first index in the array that is >= value, or arr.size() if no
// such index exists
int firstAtLeast(const vector<int> &arr, int value) {
	int lo = 0, hi = arr.size();
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (arr[mid] >= value) hi = mid;
		else lo = mid + 1;
	}
	return lo;
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> cities, towers;

	for (int i = 0; i < n; i++) {
		int city;
		cin >> city;
		cities.push_back(city);
	}

	for (int i = 0; i < m; i++) {
		int tower;
		cin >> tower;
		towers.push_back(tower);
	}

	int minR = 0;
	for (int i = 0; i < n; i++) {
		int towerRight = firstAtLeast(towers, cities[i]);
		int towerLeft = towerRight - 1;

		int minRForThisCity = 2e9;
		if (towerRight < m) {
			assert(towers[towerRight] >= cities[i]);
			minRForThisCity =
			    min(minRForThisCity, towers[towerRight] - cities[i]);
		}
		if (towerLeft >= 0) {
			assert(towers[towerLeft] <= cities[i]);
			minRForThisCity =
			    min(minRForThisCity, cities[i] - towers[towerLeft]);
		}

		minR = max(minR, minRForThisCity);
	}

	cout << minR << endl;
}

学习代码：Set，实则也是二分

#include <algorithm>
#include <iostream>
#include <set>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	int cities[n];
	set<int> towers;
	int tower;
	for (int i = 0; i < n; i++) { cin >> cities[i]; }
	for (int i = 0; i < m; i++) {
		cin >> tower;
		towers.insert(tower);
	}
	int r = 0;
	for (int i = 0; i < n; i++) {
		int dist = 2e9 + 1;
		// find closest tower to the right of the city
		auto closesttower = towers.lower_bound(cities[i]);
		if (closesttower != towers.end()) {
			// if a tower is found, update the distance
			dist = *closesttower - cities[i];
		}
		// find closest tower to the left of the city
		if (closesttower != towers.begin()) {
			closesttower--;
			// update dist with the minimum of the distances
			dist = min(dist, cities[i] - *closesttower);
		}
		r = max(r, dist);
	}
	cout << r << endl;
	return 0;
}