给定 n 个闭区间 [l i ,r i ]。你需要在数轴上选择一个整数点的集合 P={p 1 ,p 2 ,…,p k }，满足以下两个条件： 对于每一个给定的区间 [l i ,r i ]，都至少存在一个你选择的点 p j ∈P，使得 l i ≤p j ≤r i 。 定义一个选择 P 的方案的总成本为 j=1 ∑ k p j 。总成本需要达到最小。 你需要计算出这个最小的总成本。 输入 第一行包含一个整数 n，表示区间的数量。 接下来 n 行，每行包含两个整数 l i 和 r i ，描述一个区间的左右端点。 输出 输出一个整数，表示满足条件的最小总成本。 样例输入 复制 3 1 5 3 7 6 8 样例输出 复制 7 提示 样例解释 选择点 1,6 可以获得最小的总成本，答案为 1+6=7。 数据范围与约定 对于 100% 的数据，满足 1≤n≤10 5 ，1≤l i ≤r i ≤10 9 ；

以下是解决该问题的Python代码： ```python # 读取输入 n = int(input()) # 存储区间的列表 intervals = [] for _ in range(n): l, r = map(int, input().split()) intervals.append((l, r)) # 按照区间的右边界从小到大排序 intervals.sort(key=lambda x: x[1]) # 存储选择的点 selected_points = [] # 遍历每个区间 for l, r in intervals: # 检查是否已经有选择的点在当前区间内 found = False for point in selected_points: if l <= point <= r: found = True break # 如果没有找到点在当前区间内，则选择该区间的右边界作为新的点 if not found: selected_points.append(r) # 计算选择的点的总成本 total_cost = sum(selected_points) print(total_cost) ``` 代码解释： 1. 输入读取：首先读取区间的数量 `n`，然后循环 `n` 次，每次读取一个区间的左右边界，并将其存储在 `intervals` 列表中。 2. 区间排序：使用 `sort` 方法按照区间的右边界从小到大对 `intervals` 列表进行排序。这样做的目的是优先选择右边界较小的区间，因为选择右边界的点可以覆盖尽可能多的后续区间。 3. 选择点：遍历排序后的区间列表，对于每个区间，检查是否已经有选择的点在该区间内。如果没有，则选择该区间的右边界作为新的点，并将其添加到 `selected_points` 列表中。 4. 计算总成本：使用 `sum` 函数计算 `selected_points` 列表中所有点的总和，并将其作为最小总成本输出。 复杂度分析： - 时间复杂度：排序操作的时间复杂度为 $O(n log n)$，遍历区间列表的时间复杂度为 $O(n^2)$，因此总的时间复杂度为 $O(n^2)$。 - 空间复杂度：主要使用了 `intervals` 和 `selected_points` 两个列表，空间复杂度为 $O(n)$。 [2025-12-13 10:58:42 | AI问答 | 500点数解答]