一条笔直的路从 0 到 L，路边有 n 盏路灯。
第 i 盏路灯在位置 pᵢ，现在照亮 pᵢ − rᵢ 到 pᵢ + rᵢ（含两端）。
可以给所有路灯装上同样强度 t 的增幅器。
t 是不小于 0 的整数，装上后每盏路灯照亮 pᵢ − rᵢ − t 到 pᵢ + rᵢ + t。
最多只能打开 k 盏路灯。
如果打开的路灯照亮的区间合起来包含 0 到 L 之间的所有点（包括非整数点），就算把路全部照亮了。
两个区间只在一个端点相遇时，它们之间也没有空隙。
输出能把路全部照亮的最小 t。
4 10 2 1 1 4 2 9 0 7 1
2
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
t 变大只会让所有区间变宽，所以 t 可行则 t + 1 也可行。
因此对答案 t 二分查找：从 lo = 0、hi = L 开始（t = L 时路上任意一盏灯都能照亮整个 [0, L]），mid 可行就 hi = mid，不可行就 lo = mid + 1，最后 lo 就是答案。
判断某个 t 是否可行用贪心：在能照到尚未照亮的最左点 need（开始是 0）的路灯中，打开右端最远的那盏，把 need 移到那个右端，最多重复 k 次。
所有区间都加长同样的 t，所以左端 p − r 的顺序与 t 无关——开头排序一次，每次判断从前往后扫一遍即可（n log n + 31 × n）。
陷阱一：区间是闭区间，端点刚好相接也算连上（左端 − t <= need）。
写成 < 会把 [−1, 5] 和 [5, 11] 当成不相连，答案就变大了。
陷阱二：p + r 最多 20 亿，勉强放进 32 位 int（约 21 亿），但查找时加上 t 会到 30 亿而溢出。
C、C++ 需要 long long，Java、C# 需要 long；Python 整数没有上限，JavaScript、TypeScript、Craykon 的数是双精度浮点数，直接用就行。
陷阱三：按位置 p 排序路灯，在半径不同时与左端的顺序不一致，从前往后扫时会漏掉左端更小的路灯。
陷阱四：用 hi = mid - 1 丢掉可行的 mid 会跳过答案——答案候选要始终留在 [lo, hi] 里。
排序各语言不同：Python 直接对元组 (p - r, p + r) 调用 sort()；JavaScript、TypeScript 要写 sort((x, y) => x[0] - y[0])（没有比较函数会按字符串比较）；Java Arrays.sort(lamps, (x, y) -> Long.compare(x[0], y[0]))；C# Array.Sort(lamps, (x, y) => x.left.CompareTo(y.left))；C++ 直接用 std::sort 排 std::pair；C 的 qsort 比较函数若以 int 返回 x - y 可能溢出，要返回 (x > y) - (x < y)。
Craykon 像 lamps.排序(左端顺序) 这样传入返回负数、0、正数的函数，整数除法是 数学.商(lo + hi, 2)。
import sys data = sys.stdin.read().split()n, length, k = int(data[0]), int(data[1]), int(data[2])lamps = [] # (p - r, p + r): 늘이기 전에 비추는 구간for i in range(n): p, r = int(data[3 + 2 * i]), int(data[4 + 2 * i]) lamps.append((p - r, p + r))lamps.sort() # 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 def lamps_needed_ok(t): """모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가.""" need = 0 # 아직 비춘다고 확인하지 못한 가장 왼쪽 점 i = 0 best = -1 # 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 used = 0 while used < k: while i < n and lamps[i][0] - t <= need: # 끝이 닿기만 해도 이어진다(닫힌 구간) best = max(best, lamps[i][1] + t) i += 1 if best < need: # need를 비추는 등이 없다 return False used += 1 if best >= length: return True if best == need: # 더 나아갈 수 없다 return False need = best return False lo, hi = 0, length # t = length이면 어느 등 하나로도 [0, length]를 다 비춘다while lo < hi: mid = (lo + hi) // 2 if lamps_needed_ok(mid): hi = mid else: lo = mid + 1print(lo)const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, length, k] = data;const lamps = []; // [p - r, p + r]: 늘이기 전에 비추는 구간for (let i = 0; i < n; i++) { const p = data[3 + 2 * i], r = data[4 + 2 * i]; lamps.push([p - r, p + r]);}lamps.sort((x, y) => x[0] - y[0]); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가function canCover(t) { let need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 let i = 0; let best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (let used = 1; used <= k; used++) { while (i < n && lamps[i][0] - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간) best = Math.max(best, lamps[i][1] + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best === need) return false; // 더 나아갈 수 없다 need = best; } return false;} let lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다while (lo < hi) { const mid = Math.floor((lo + hi) / 2); if (canCover(mid)) hi = mid; else lo = mid + 1;}console.log(lo);import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, length, k] = data;const lamps: [left: number, right: number][] = []; // 늘이기 전에 비추는 구간 [p - r, p + r]for (let i = 0; i < n; i++) { const p = data[3 + 2 * i], r = data[4 + 2 * i]; lamps.push([p - r, p + r]);}lamps.sort((x, y) => x[0] - y[0]); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가function canCover(t: number): boolean { let need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 let i = 0; let best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (let used = 1; used <= k; used++) { while (i < n && lamps[i][0] - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간) best = Math.max(best, lamps[i][1] + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best === need) return false; // 더 나아갈 수 없다 need = best; } return false;} let lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다while (lo < hi) { const mid: number = Math.floor((lo + hi) / 2); if (canCover(mid)) hi = mid; else lo = mid + 1;}console.log(lo);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; public class Main { static int n, k; static long length; static long[][] lamps; // {p - r, p + r}: 늘이기 전에 비추는 구간. p + r + t는 30억까지라 long // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가 static boolean canCover(long t) { long need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 int i = 0; long best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (int used = 1; used <= k; used++) { while (i < n && lamps[i][0] - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간) best = Math.max(best, lamps[i][1] + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best == need) return false; // 더 나아갈 수 없다 need = best; } return false; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); n = Integer.parseInt(st.nextToken()); length = Long.parseLong(st.nextToken()); k = Integer.parseInt(st.nextToken()); lamps = new long[n][]; for (int i = 0; i < n; i++) { st = new StringTokenizer(in.readLine()); long p = Long.parseLong(st.nextToken()); long r = Long.parseLong(st.nextToken()); lamps[i] = new long[] {p - r, p + r}; } // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 Arrays.sort(lamps, (x, y) -> Long.compare(x[0], y[0])); long lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다 while (lo < hi) { long mid = (lo + hi) / 2; if (canCover(mid)) hi = mid; else lo = mid + 1; } System.out.println(lo); }}using System; class Program{ static int n, k; static long length; static (long left, long right)[] lamps; // 늘이기 전에 비추는 구간 [p - r, p + r]. p + r + t는 30억까지라 long // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가 static bool CanCover(long t) { long need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 int i = 0; long best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (int used = 1; used <= k; used++) { while (i < n && lamps[i].left - t <= need) // 끝이 닿기만 해도 이어진다(닫힌 구간) { best = Math.Max(best, lamps[i].right + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best == need) return false; // 더 나아갈 수 없다 need = best; } return false; } static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); n = int.Parse(first[0]); length = long.Parse(first[1]); k = int.Parse(first[2]); lamps = new (long left, long right)[n]; for (int i = 0; i < n; i++) { string[] w = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long p = long.Parse(w[0]), r = long.Parse(w[1]); lamps[i] = (p - r, p + r); } // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 Array.Sort(lamps, (x, y) => x.left.CompareTo(y.left)); long lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다 while (lo < hi) { long mid = (lo + hi) / 2; if (CanCover(mid)) hi = mid; else lo = mid + 1; } Console.WriteLine(lo); }}#include <algorithm>#include <iostream>#include <utility>#include <vector> int n, k;long long length;std::vector<std::pair<long long, long long>> lamps; // (p - r, p + r): 늘이기 전에 비추는 구간. p + r + t는 30억까지라 long long // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가bool canCover(long long t) { long long need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 int i = 0; long long best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (int used = 1; used <= k; used++) { while (i < n && lamps[i].first - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간) best = std::max(best, lamps[i].second + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best == need) return false; // 더 나아갈 수 없다 need = best; } return false;} int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> n >> length >> k; lamps.resize(n); for (auto& lamp : lamps) { long long p, r; std::cin >> p >> r; lamp = {p - r, p + r}; } std::sort(lamps.begin(), lamps.end()); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 long long lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다 while (lo < hi) { long long mid = (lo + hi) / 2; if (canCover(mid)) hi = mid; else lo = mid + 1; } std::cout << lo << '\n'; return 0;}#include <stdio.h>#include <stdlib.h> #define MAXN 10000 typedef struct { long long left, right; /* 늘이기 전에 비추는 구간 [p - r, p + r]. p + r + t는 30억까지라 long long */} Lamp; static Lamp lamps[MAXN];static int n, k;static long long length; static int byLeft(const void* a, const void* b) { long long x = ((const Lamp*)a)->left, y = ((const Lamp*)b)->left; return (x > y) - (x < y); /* x - y를 int로 돌려주면 넘칠 수 있다 */} /* 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있으면 1 */static int canCover(long long t) { long long need = 0; /* 아직 비춘다고 확인하지 못한 가장 왼쪽 점 */ long long best = -1; /* 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 */ int i = 0; for (int used = 1; used <= k; used++) { while (i < n && lamps[i].left - t <= need) { /* 끝이 닿기만 해도 이어진다(닫힌 구간) */ if (lamps[i].right + t > best) best = lamps[i].right + t; i++; } if (best < need) return 0; /* need를 비추는 등이 없다 */ if (best >= length) return 1; if (best == need) return 0; /* 더 나아갈 수 없다 */ need = best; } return 0;} int main(void) { if (scanf("%d %lld %d", &n, &length, &k) != 3) return 0; for (int i = 0; i < n; i++) { long long p, r; scanf("%lld %lld", &p, &r); lamps[i].left = p - r; lamps[i].right = p + r; } qsort(lamps, n, sizeof lamps[0], byLeft); /* 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 */ long long lo = 0, hi = length; /* t = length이면 어느 등 하나로도 [0, length]를 다 비춘다 */ while (lo < hi) { long long mid = (lo + hi) / 2; if (canCover(mid)) hi = mid; else lo = mid + 1; } printf("%lld\n", lo); return 0;}// 모든 등을 t만큼 늘였을 때 k개 이하로 [0, 길이]를 다 비출 수 있는가비출수있나(lamps, 길이, k, t){ need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 i = 0; best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 循环 (used = 1; used <= k; used++) { 当 (i < lamps.数量 && lamps[i][0] - t <= need) { best = 数学.较大值(best, lamps[i][1] + t); i++; } 如果 (best < need) { 返回 假; } 如果 (best >= 길이) { 返回 真; } 如果 (best == need) { 返回 假; } need = best; } 返回 假;} 왼쪽끝순(앞, 뒤){ 返回 앞[0] - 뒤[0];} 첫줄 = 控制台.读数字();n = 첫줄[0];길이 = 첫줄[1];k = 첫줄[2];lamps = []; // [p - r, p + r]: 늘이기 전에 비추는 구간循环 (j = 0; j < n; j++){ 등 = 控制台.读数字(); lamps.添加([등[0] - 등[1], 등[0] + 등[1]]);}lamps.排序(왼쪽끝순); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 lo = 0;hi = 길이; // t = 길이이면 어느 등 하나로도 [0, 길이]를 다 비춘다当 (lo < hi){ mid = 数学.商(lo + hi, 2); 如果 (비출수있나(lamps, 길이, k, mid)) { hi = mid; } 否则 { lo = mid + 1; }}控制台.输出(lo);