刷题笔记合集🔗

问题描述

小基是一名基站维护工程师，负责管理一片区域内的基站。这片区域可以看作是一个二维平面，每个基站都有一个坐标 和一个信号覆盖半径 。一个基站可以覆盖到所有与其距离不超过 的点。

现在，小基需要检修一些基站。由于检修资源有限，他希望选择尽可能少的基站进行检修，同时确保所有指定的服务点都能被这些检修后的基站覆盖到。

请你帮助小基计算最少需要检修多少个基站。

输入格式

第一行包含两个整数 和 ，分别表示基站的数量和服务点的数量。

接下来的 行，每行包含三个整数 、 和 ，表示第 个基站的坐标 和信号覆盖半径 。

接下来的 行，每行包含两个整数 和 ，表示第 个服务点的坐标 。

输出格式

输出一个整数，表示最少需要检修的基站数量。如果无法覆盖所有服务点，则输出 。

样例输入1

3 3
0 0 5
10 0 5
5 5 5
1 1
8 1
5 6

样例输出1

2

样例输入2

2 3
0 0 5
10 0 5
1 1
8 1
20 20

样例输出2

-1

样例输入3

4 5
0 0 5
10 0 5
5 5 5
15 5 5
1 1
8 1
5 6
12 3
16 6

样例输出3

3

样例解释

数据范围

题解

这道题目本质上是一个集合覆盖问题。需要选择最少数量的基站，使得所有服务点都被覆盖。

首先，需要确定每个基站可以覆盖哪些服务点。对于基站 和服务点 ，如果它们之间的欧几里得距离不超过基站的覆盖半径 ，即 ，那么这个基站可以覆盖这个服务点。

接下来，可以使用贪心算法来解决这个问题：

1. 对于每个基站，计算它可以覆盖的服务点集合。
2. 每次选择能覆盖最多未覆盖服务点的基站。
3. 重复步骤2，直到所有服务点都被覆盖，或者没有基站可以覆盖更多的服务点。

这个贪心策略虽然不一定能得到最优解，但在实际问题中通常表现良好。对于本题的数据范围，这种方法是可行的。

时间复杂度分析：

• 计算每个基站可以覆盖的服务点需要 的时间。
• 贪心选择基站的过程最多需要 的时间。
• 因此，总时间复杂度为 。

对于给定的数据范围 ()，这个复杂度是可以接受的。

参考代码

import math

def get_len(p1, p2):
    """
    计算两点之间的欧几里得距离
    
    参数:
        p1: 第一个点的坐标 (x, y)
        p2: 第二个点的坐标 (a, b)
    
    返回:
        两点之间的距离
    """
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

def solve_prob():
    """
    找出最少需要检修的基站数量
    
    返回:
        最少需要检修的基站数量，如果无法覆盖所有服务点则返回-1
    """
    # 读取基站数量和服务点数量
    n_bs, n_sp = map(int, input().split())
    
    # 读取基站信息
    bs_data = []
    for _ in range(n_bs):
        x, y, r = map(int, input().split())
        bs_data.append((x, y, r))
    
    # 读取服务点信息
    sp_data = []
    for _ in range(n_sp):
        a, b = map(int, input().split())
        sp_data.append((a, b))
    
    # 计算每个基站可以覆盖的服务点
    cov_map = [[] for _ in range(n_bs)]
    
    # 遍历所有基站
    for i in range(n_bs):
        x, y, r = bs_data[i]
        # 遍历所有服务点
        for j in range(n_sp):
            a, b = sp_data[j]
            # 如果服务点在基站覆盖范围内，则添加到覆盖列表
            if get_len((x, y), (a, b)) <= r:
                cov_map[i].append(j)
    
    # 使用贪心算法选择基站
    cnt = 0
    cov = set()
    
    # 当还有未覆盖的服务点时继续选择基站
    while len(cov) < n_sp:
        best = -1
        best_add = set()
        
        # 找出能覆盖最多未覆盖服务点的基站
        for i in range(n_bs):
            # 计算当前基站可以新覆盖的服务点
            new_add = set(cov_map[i]) - cov
            if len(new_add) > len(best_add):
                best = i
                best_add = new_add
        
        # 如果没有基站可以覆盖更多的服务点，则无法覆盖所有服务点
        if best == -1:
            return -1
        
        # 选择当前最优的基站
        cnt += 1
        cov |= best_add
    
    return cnt

# 主函数
if __name__ == "__main__":
    print(solve_prob())

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_set>
using namespace std;

/**
 * 计算两点之间的欧几里得距离
 * 
 * @param x1 第一个点的x坐标
 * @param y1 第一个点的y坐标
 * @param x2 第二个点的x坐标
 * @param y2 第二个点的y坐标
 * @return 两点之间的距离
 */
double dist(int x1, int y1, int x2, int y2) {
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

/**
 * 检查是否可以覆盖所有服务点
 * 
 * @param n 基站数量
 * @param m 服务点数量
 * @para