CF1253E Antenna Coverage

中央镇的市长希望对中央大街进行现代化改造，在本题中，中央大街用 $ (Ox) $ 轴表示。 在这条街上有 $ n $ 个天线，编号从 $ 1 $ 到 $ n $。第 $ i $ 个天线位于位置 $ x_i $，初始覆盖范围为 $ s_i $：它可以覆盖区间 $ [x_i - s_i,\, x_i + s_i] $ 内的所有整数位置。 你可以将任意天线的覆盖范围增加 $ 1 $，每次操作花费 $ 1 $ 个金币。你可以对同一个天线进行多次操作。 为了完成街道的现代化，需要使得所有从 $ 1 $ 到 $ m $ 的整数位置都被至少一个天线覆盖。注意，允许覆盖 $ [1,\, m] $ 以外的位置，即使这些位置不需要被覆盖。 请问，最少需要多少金币，才能完成这项现代化改造？

无

无

在第一个样例中，一种可行的策略如下： - 将第一个天线的覆盖范围增加 $ 40 $，使其变为 $ 2 + 40 = 42 $。此时该天线覆盖区间 $ [43 - 42,\, 43 + 42] $，即 $ [1,\, 85] $。 - 将第二个天线的覆盖范围增加 $ 210 $，使其变为 $ 4 + 210 = 214 $。此时该天线覆盖区间 $ [300 - 214,\, 300 + 214] $，即 $ [86,\, 514] $。 - 将第三个天线的覆盖范围增加 $ 31 $，使其变为 $ 10 + 31 = 41 $。此时该天线覆盖区间 $ [554 - 41,\, 554 + 41] $，即 $ [513,\, 595] $。 总代价为 $ 40 + 210 + 31 = 281 $。可以证明，这是使得所有 $ 1 $ 到 $ 595 $ 的位置都被至少一个天线覆盖所需的最小代价。 注意，在本方案中，位置 $ 513 $ 和 $ 514 $ 被不同的天线重复覆盖，但这并不影响结果。 —— 在第二个样例中，第一个天线已经覆盖了区间 $ [0,\, 2] $，因此无需进行任何操作。 注意，唯一需要被覆盖的位置是 $ 1 $；位置 $ 0 $ 和 $ 2 $ 也被覆盖了，但这并不重要。 由 ChatGPT 4.1 翻译