解题思路:
从线段的起点向终点安装喷水头, 令 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;
- }
来源: http://www.bubuko.com/infodetail-2735055.html