今天就准备了一道题
问题描述
2345 年 4 月 13 日，蓝桥杯省赛即将开办。参与本届蓝桥杯的人数高达 1414 亿人。每位参赛选手都使用一台编号唯一的电脑参赛，编号从 1 到 14000000001400000000。所有电脑按编号顺序排列成一排。
为了保障网络安全，大赛组委会事先在 NN 台电脑（编号 A1,A2,…,ANA1,A2,…,AN）上安装了防火墙软件。
开赛在即，有情报显示，本次比赛共会有 MM 台电脑（编号 B1,B2,…,BMB1,B2,…,BM）遭受到 DDOS 攻击，这 MM 台电脑的编号分别为 B1,B2,…,BMB1,B2,…,BM。
只有安装了防火墙的电脑才能抵御 DDOS 攻击。对此，组委会设计了一种共享机制：已安装防火墙的电脑可以通过数据线与相邻电脑连接，并共享其防火墙保护。
请问，要保护所有将遭受攻击的电脑，至少需要多少条数据线？
输入格式
第一行输入两个整数 NN 和 MM（1≤N,M≤1051≤N,M≤105），表示已安装防火墙的电脑数量和将遭受攻击的电脑数量。
第二行输入 NN 个整数 A1,A2,…,ANA1,A2,…,AN（1≤Ai≤1091≤Ai≤109），表示安装了防火墙的电脑编号。
第三行输入 MM 个整数 B1,B2,…,BMB1,B2,…,BM（1≤Bi≤1091≤Bi≤109），表示将遭受攻击的电脑编号。
数据保证 A1,A2,…,ANA1,A2,…,AN 各不相同，B1,B2,…,BMB1,B2,…,BM 各不相同。
输出格式
输出一个整数，表示保护所有将遭受攻击的电脑所需的最少的数据线的数量。
样例输入 1
5 3
1 2 3 4 5
1 2 3
样例输出 1
0
样例输入 2
3 1
1 2 3
4
样例输出 2
1答案
import os
import sys
from math import inf
import bisect
# 因为电脑的数量很多，故思路一定是从 遭受攻击 的 M 台电脑出发，寻找出口
# 对于每台受到攻击的电脑，我们肯定是向左或向右扩展到最近的有防火墙的电脑上
# 为了方便讨论，我们可以将受到攻击的电脑 按照 编号从小到大进行考虑
# 对于受到攻击的电脑 i 来说，要么向左找最近的 装有防火墙的电脑
# 要么向右找最近的 装有防火墙的电脑 或 受到攻击的电脑
# 特殊情况: 可能所有受到攻击的电脑 都与 右边 受到攻击的电脑 相连接 但是 最右边没有 保护的电脑
# 此时，最优的选择应该是 所有连接的受到攻击的电脑 的最左边的电脑 与 左边的保护电脑相连接
# 故 我们需要 做的就是 对于没有 有受到攻击电脑的区间 去对区间进行最优分解即可
# 对于 电脑 i 来说，如果电脑 i 是连接左端的防火墙电脑 那么 同一个区间内的电脑 i + 1 就一定是连接右端的防火墙电脑
# 故 i 到左端的距离 与 i + 1 到右端的距离就是这个区间的解 我们只要把每个区间最优解相加就是全局最优解
# 故我们可以用一个分组循环解决 ----- 外层循环只关注 ---> 边界的选择
# 内层循环只关注 ---> 处理边界的最优解
# 思考最优解是如何构成的 ---- 每次枚举的点就是与右节点连接的点，上一个节点是与左端点相连接的点
# 故我们只需要在枚举的时候 维护 一个上一个节点的值的变量即可
n, m = list(map(int, input().split()))
a_number = list(map(int, input().split()))
b_number = list(map(int, input().split()))
# 题目保证 A 内的点不相同， B 内的点不相同，故不用进行去重处理
a_number.sort()
b_number.sort()
# 为 a_number 左端与右端添加哨兵节点
a_number = [-10 ** 9-1] + a_number + [10 ** 9 + 1]
res = 0
index = 0
while index < m:
# 确定边界
value = b_number[index]
right_index = bisect.bisect_right(a_number, value)
left_index = right_index - 1
right_number = a_number[right_index]
left_number = a_number[left_index]
# 维护信息
pre = left_number # 上一个节点选的值，起始为左边界节点
ans = inf # 局部最优解
while index < m and left_number <= b_number[index] <= right_number: # 枚举在区间中的节点
ans = min(ans, pre - left_number + right_number - b_number[index])
pre = b_number[index]
if index + 1 == m or b_number[index + 1] > right_number: # 下一个节点不符合条件了，将当前节点与左端点相连
ans = min(ans, b_number[index] - left_number)
index += 1
res += ans # 更新全局最优解
print(res)