描述
农夫约翰的牛发现，在他的田里沿着山脊生长的三叶草是特别好的。为了给三叶草浇水，农夫约翰在山脊上安装了喷水器。
为了使安装更容易，每个喷头必须安装在山脊上(我们可以认为这是一条长度为L(1<=L<=1，000，000)的一维数列；L是偶数)。
每个洒水器沿山脊向两个方向地面排水一段距离。每个喷雾半径是A.B范围内的整数(1<=A<=B<=1000)。农夫约翰需要给整个山脊浇水，用一个喷头覆盖整个山脊上的每一个位置。此外，FJ不会在任何一个方向超过山脊的末端。
每头农场主约翰的N(1<=N<=1000)奶牛都有她特别喜欢的一系列三叶草(这些范围可能重叠)。范围由闭区间(S，E)定义。母牛的每一个选择范围都必须用一个喷头浇水，这种喷头可能会也可能不会在给定的范围内喷水。
找出最小数量的喷头需要浇水整个山脊没有重叠。
为了使安装更容易，每个喷头必须安装在山脊上(我们可以认为这是一条长度为L(1<=L<=1，000，000)的一维数列；L是偶数)。
每个洒水器沿山脊向两个方向地面排水一段距离。每个喷雾半径是A.B范围内的整数(1<=A<=B<=1000)。农夫约翰需要给整个山脊浇水，用一个喷头覆盖整个山脊上的每一个位置。此外，FJ不会在任何一个方向超过山脊的末端。
每头农场主约翰的N(1<=N<=1000)奶牛都有她特别喜欢的一系列三叶草(这些范围可能重叠)。范围由闭区间(S，E)定义。母牛的每一个选择范围都必须用一个喷头浇水，这种喷头可能会也可能不会在给定的范围内喷水。
找出最小数量的喷头需要浇水整个山脊没有重叠。
输入
*第1行：两个空格分隔的整数：n和L
*第2行：两个空格分隔的整数：A和B
* Lines 3..N+2: Each line contains two integers, S and E (0 <= S < E <= L) specifying the start end location respectively of a range preferred by some cow. Locations are given as distance from the start of the ridge and so are in the range 0..L.
*第2行：两个空格分隔的整数：A和B
* Lines 3..N+2: Each line contains two integers, S and E (0 <= S < E <= L) specifying the start end location respectively of a range preferred by some cow. Locations are given as distance from the start of the ridge and so are in the range 0..L.
输出量
*第1行：所需的最少喷头数目。如果不可能为农民约翰设计喷头配置，输出-1。
样本输入
2 8 1 2 6 7 3 6
样本输出
3
暗示
输入详情：
两头母牛沿着一条8长的山脊。喷头在1.2(即1或2)范围内有整数的喷雾半径。一只母牛喜欢3-6的范围，另一只喜欢6-7的范围。
产出详情：
需要三个喷头：一个喷淋距离为1，一个喷淋距离为4，喷雾距离为2，另一个喷淋距离为7，喷雾距离为1。第二个洒水器像第二头牛(3-6)一样，将整个范围内的三叶草全部浇水。最后的洒水所有的范围内的三叶草喜欢的第一头牛(6-7)。下面是一个图表：
喷头在2和6处不被认为是重叠的。
两头母牛沿着一条8长的山脊。喷头在1.2(即1或2)范围内有整数的喷雾半径。一只母牛喜欢3-6的范围，另一只喜欢6-7的范围。
产出详情：
需要三个喷头：一个喷淋距离为1，一个喷淋距离为4，喷雾距离为2，另一个喷淋距离为7，喷雾距离为1。第二个洒水器像第二头牛(3-6)一样，将整个范围内的三叶草全部浇水。最后的洒水所有的范围内的三叶草喜欢的第一头牛(6-7)。下面是一个图表：
|-----c2----|-c1| cows' preferred ranges
|---1---|-------2-------|---3---| sprinklers
+---+---+---+---+---+---+---+---+
0 1 2 3 4 5 6 7 8
喷头在2和6处不被认为是重叠的。
解题思路：
从线段的起点向终点安装喷水头，令f(X)表示：所安装喷水头的喷洒范围 恰好覆盖直线上的区间[0 X]时，最少需要多少个喷水头
显然，X应满足下列条件：
X为偶数
X所在位置不会出现奶牛，即X不属于任何一个(S,E)
X>=2A
当X<=2B时，存在Y属于[X-2B X-2A]且Y满足上述三个条件，使得 f(X)=f(Y)+1
对每个X求f(X)，都要遍历区间 [X-2B, X -2A]去寻找其中最小的 f(Y),则时间复杂度为：L * B = 1000000 * 1000，太慢，快速找到[X-2B X-2A]中使得f(Y)最小的元素是问题求解速度的关键 。
！！！
可以使用优先队列priority_queue! (multiset也可以，比 priority_queue慢一点）!
求F(X)时，若坐标属于[X-2B, X-2A]的二元组(i,F(i))都保存在 一个priority_queue中,并根据F(i)值排序，则队头的元素就能 确保是F(i)值最小的。在求X点的F(x)时，必须确保队列中包含所有属于 [X-2B,X-2A]的点。 而且，不允许出现坐标大于X-2A的点，因为这样的点对求F(X)无用，如果这样的点出现在队头，因其对求后续点的F值有用，故不能抛弃之，于是算法就无法继续了。
队列中可以出现坐标小于 X-2B 的点。这样的点若出现在队头，则直接将其抛弃。
求出X点的F值后，将(X-2A+2, F(X-2A+2))放入队列，为求F(X+2)作准备
代码：
#include<iostream> #include<queue> using namespace std; const int INF = 0x3f3f3f; const int MAXL = 1000010; int cowThere[MAXL];//cowThere[i]为1表示点i有奶 int dp[MAXL];// dp[L]就是答案 struct Fx { int x; int f; bool operator<(const Fx & a) const { return f > a.f; } Fx(int xx=0,int ff=0):x(xx),f(ff) { } };// 在优先队列里，f值越小的越优先 priority_queue<Fx> qFx; int main() { int N, L, A, B; cin >> N >> L; cin>> A >> B;//A,B的定义变为覆盖的直径 A <<= 1; B <<= 1; for(int i = 0; i < N; i++) { int s, e; cin >> s >> e; cowThere[s+1]++;//从s+1进入一个奶牛区 cowThere[e]--;//从e起退出一个奶牛区 } int inCows = 0; //表示当前点位于多少头奶牛的活动范围之内 for(int i = 0; i <= L; i++) {//算出每个点是否有奶牛 dp[i] = INF; inCows += cowThere[i]; cowThere[i] = inCows > 0; } for(int i = A; i <= B; i += 2) {//初始化队列 if(!cowThere[i]) { dp[i] = 1; if(i <= B + 2 - A) {//在求dp[i]的时候，要确保队列里的点x，x <= i - A qFx.push(Fx(i, 1)); } } } for(int i = B + 2; i <= L; i += 2) { if(!cowThere[i]) { Fx fx; while(!qFx.empty()) { fx = qFx.top(); if(fx.x < i - B) qFx.pop(); else break; } if(!qFx.empty()) { dp[i] = fx.f + 1; } } //队列中增加一个可达下个点的点，为下一个dp(i+2)做准备 if(dp[i + 2 - A] != INF) qFx.push(Fx(i + 2 - A, dp[i + 2 - A])); } if(dp[L] == INF) cout << -1 << endl; else cout << dp[L] << endl; return 0; }