A7070. Welcome24ever 和喷灌器
编程题
提高+/省选-
知识点
题目描述
Welcome24ever 的奶牛们发现山脊上的草特别美味。为维持草的生长，Welcome24ever 打算在山脊上安装若干喷灌器。
将山脊看成一条一维数轴，范围为 $[0,L]$，其中 $L$ 为偶数，且 $1 \le L \le 10^6$。
每个喷灌器必须满足：
- 位置是整数 $p$；
- 射程（半径）是整数 $x$，且 $A \le x \le B$（$1 \le A \le B \le 10^3$）；
- 它的灌溉范围是 $[p-x,\,p+x]$，并且必须完全落在山脊范围内，即 $0 \le p-x$ 且 $p+x \le L$。
现在要求：
1. 山脊上的每一个位置都必须被灌溉到；
2. 任意两个喷灌器的灌溉区间不允许重叠（端点相接不算重叠）；
3. 有 $N$ 只奶牛（$1 \le N \le 10^3$），第 $i$ 只奶牛最喜欢的草区是区间 $[S_i,E_i]$（$1 \le S_i < E_i \le L$），不同奶牛的草区可以重叠；
4. 每只奶牛的草区必须“只被一个喷灌器灌溉”，也就是说：对每个 $i$，存在某个喷灌器的灌溉区间完全覆盖 $[S_i,E_i]$。
请你求出最少需要多少个喷灌器；如果无法做到，输出 $-1$。
将山脊看成一条一维数轴，范围为 $[0,L]$，其中 $L$ 为偶数，且 $1 \le L \le 10^6$。
每个喷灌器必须满足：
- 位置是整数 $p$；
- 射程（半径）是整数 $x$，且 $A \le x \le B$（$1 \le A \le B \le 10^3$）；
- 它的灌溉范围是 $[p-x,\,p+x]$，并且必须完全落在山脊范围内，即 $0 \le p-x$ 且 $p+x \le L$。
现在要求：
1. 山脊上的每一个位置都必须被灌溉到；
2. 任意两个喷灌器的灌溉区间不允许重叠（端点相接不算重叠）；
3. 有 $N$ 只奶牛（$1 \le N \le 10^3$），第 $i$ 只奶牛最喜欢的草区是区间 $[S_i,E_i]$（$1 \le S_i < E_i \le L$），不同奶牛的草区可以重叠；
4. 每只奶牛的草区必须“只被一个喷灌器灌溉”，也就是说：对每个 $i$，存在某个喷灌器的灌溉区间完全覆盖 $[S_i,E_i]$。
请你求出最少需要多少个喷灌器；如果无法做到，输出 $-1$。
输入格式
第一行包含两个整数 $N, L$。
第二行包含两个整数 $A, B$。
接下来 $N$ 行，每行包含两个整数 $S_i, E_i$。
第二行包含两个整数 $A, B$。
接下来 $N$ 行，每行包含两个整数 $S_i, E_i$。
输出格式
输出一行一个整数，表示最少喷灌器数量；如果无解输出 $-1$。
输入输出样例
输入 #1
2 8 1 2 6 7 3 6
输出 #1
3
说明/提示
### 样例解释
由于半径 $x$ 满足 $1 \le x \le 2$，所以每个喷灌器覆盖的区间长度只能是 $2$ 或 $4$。
奶牛草区 $[3,6]$ 要求“只被一个喷灌器灌溉”，因此分界点不能落在 $(3,6)$ 内，也就是 **$4$、$5$ 不能作为分割点**。
一种最优划分为：
- $[0,2]$
- $[2,6]$
- $[6,8]$
共需要 $3$ 个喷灌器，并且两只奶牛的草区都各自完全落在某一段内，所以答案是 $3$。
由于半径 $x$ 满足 $1 \le x \le 2$，所以每个喷灌器覆盖的区间长度只能是 $2$ 或 $4$。
奶牛草区 $[3,6]$ 要求“只被一个喷灌器灌溉”，因此分界点不能落在 $(3,6)$ 内，也就是 **$4$、$5$ 不能作为分割点**。
一种最优划分为：
- $[0,2]$
- $[2,6]$
- $[6,8]$
共需要 $3$ 个喷灌器，并且两只奶牛的草区都各自完全落在某一段内，所以答案是 $3$。