l3-005 垃圾箱分布 (30 分)

题目描述：

在一个 $n$ 个点 $m$ 条边的无向图中，有 $k$ 个垃圾箱，每个垃圾箱可以处理一定范围内的垃圾。现在需要在图中选择一些点作为垃圾箱的位置，使得每个点到离它最近的垃圾箱的距离不超过该垃圾箱的处理范围。请你输出最少需要选择多少个点作为垃圾箱的位置。

输入格式：

第一行三个整数 $n,m,k$，表示点数，边数和垃圾箱个数。

接下来 $m$ 行，每行两个整数 $a,b$，表示点 $a$ 和点 $b$ 之间有一条无向边。

输出格式：

一个整数，表示最少需要选择多少个点作为垃圾箱的位置。

数据范围：

$1≤n≤10^5$

$1≤m≤2×10^5$

$1≤k≤n$

输入样例：

5 6 2
1 2
2 3
3 4
4 5
5 1
1 3

输出样例：

2

解题思路：

二分答案+最短路

二分答案是指二分最小的半径，使得可以用 $k$ 个垃圾箱覆盖整个图。

对于每个半径，我们可以用最短路算法求出每个点到最近的垃圾箱的距离，如果有一个点到最近的垃圾箱的距离超过了该垃圾箱的处理范围，那么就说明该半径不行，需要增大半径，否则就可以减小半径。

最短路算法可以用 Dijkstra 算法或者 Floyd 算法，但是由于 Floyd 算法的时间复杂度为 $O(n^3)$，所以在本题中不适用，我们可以使用 Dijkstra 算法，时间复杂度为 $O(mlogn)$。

C++ 代码

相关问题

l3-004 肿瘤诊断 (30 分)

l3-004 肿瘤诊断是指通过各种医学检查手段，对患者是否患有肿瘤进行诊断和判断。肿瘤是一种常见的疾病，早期发现和诊断对于治疗和预后都有很大的影响。常见的肿瘤诊断手段包括影像学检查、病理学检查、血液学检查等。在诊断过程中，医生需要综合分析患者的病史、体征、检查结果等多方面的信息，做出准确的诊断和治疗方案。

l3-002 特殊堆栈 (30 分)

题目描述

本题要求实现一个特殊堆栈，除了常规的入栈和出栈操作外，还需要支持以下操作：

peek：取出栈顶元素，但是不弹出；
min：返回当前栈中的最小值；
max：返回当前栈中的最大值。

输入格式

输入第一行给出一个正整数 N（≤10^5），是操作数。以下 N 行每行包含一个操作指令，格式如下：

push key：将 key 插入堆栈；
pop：弹出栈顶元素；
peek：取出栈顶元素，但是不弹出；
min：返回当前栈中的最小值；
max：返回当前栈中的最大值。

这里假设堆栈中没有重复元素，且输入保证不会出现不合法的操作。

输出格式

对于每个 min 和 max 操作，输出该操作返回的值，如果堆栈为空则输出 ERROR。

输入样例

10
push 3
push 2
push 1
max
pop
max
pop
max
pop
max

输出样例

3
2
3
1
ERROR

算法1

(单调栈) $O(n)$

首先，我们需要一个普通的栈来实现入栈和出栈操作。

然后，我们需要维护一个单调递减的栈，来实现最小值的查询。每次入栈时，如果当前元素小于等于栈顶元素，就将其入栈。否则，我们需要将栈顶元素弹出，直到栈顶元素小于等于当前元素，再将当前元素入栈。

同理，我们也需要维护一个单调递增的栈，来实现最大值的查询。

对于 peek 操作，我们只需要返回栈顶元素即可。

时间复杂度

每个元素最多入栈一次，出栈一次，查询一次最小值和最大值，因此总时间复杂度为 $O(n)$。

C++ 代码

算法2

(双向队列) $O(n)$

我们可以使用双向队列来维护最小值和最大值。队列中的元素是一个二元组，第一个元素是值，第二个元素是该值在栈中的出现次数。

每次入栈时，我们需要将该元素插入到双向队列中。同时，我们需要维护队列的单调性。对于最小值队列，我们需要保证队列中的元素是单调递增的。对于最大值队列，我们需要保证队列中的元素是单调递减的。

每次出栈时，我们需要将该元素从双向队列中删除。同时，我们也需要更新队列的单调性。

对于 min 和 max 操作，我们只需要返回最小值队列和最大值队列的队首元素即可。

时间复杂度

每个元素最多入队一次，出队一次，查询一次最小值和最大值，因此总时间复杂度为 $O(n)$。

C++ 代码