• 一片草场上有长度为L(1≤L≤106)(1 \leq L \leq 10^6)，且为偶数的线段
  • John的NN头奶牛在操场上沿着这条线段吃草
  • 每头奶牛的活动范围是一个开区间(S,E)(S,E)，S,ES,E都是整数
  • 不同奶牛活动范围有重叠
  • 现在要安装若干个可调节的喷水头灌溉草场，每个喷水头的工作半径在可[A,B][A,B]中调节
  • 要求喷水头满足下列要求
    • 线段上每个整点恰好位于一个喷水头的喷洒范围内
    • 每头奶牛的活动范围要位于一个喷水头的喷洒范围
    • 任何喷水头的喷洒范围不得超过线段两端

求John最少要安装多少个喷水头，若无法刚好安装则输出−1-1

问题分析

  • 从左端点向右端点安装喷水头，设F(X)F(X)表示:所安装喷水头的喷洒范围恰好覆盖直线上的区间[0,X][0,X]时，最少需要多少个喷水头
  • 显然，X满足：
    • X为偶数
    • X所在位置不会出现奶牛，即XX不属于任何一个(S,E)(S,E)
    • X≥2AX\geq2A
    • 当X>2BX>2B时，存在Y∈[X−2B,X−2A]Y\in [X-2B,X-2A]且YY满足上述三个条件使得F(X)=F(Y)+1F(X)=F(Y)+1

解题思路

递推计算F(X)F(X)

  • F(X)=∞:XF(X)=\infty:X是奇数
  • F(X)=∞:X<2AF(X)=\infty:X<2A
  • F(X)=∞:XF(X)=\infty:X处可能有奶牛出没
  • F(X)=1:2A≤X≤2BF(X)=1:2A\leq X \leq 2B，且XX位于任何奶牛活动范围之外

  • F(X)=1+minY=X−2BX−2AF(Y),YF(X)=1 +\min\limits_{Y=X-2B}^{X-2A} F(Y),Y位于任何奶牛的活动范围之外，且X>2B

    优化

    F(X)=1+minY=X−2BX−2AF(Y),YF(X)=1 +\min\limits_{Y=X-2B}^{X-2A} F(Y),Y位于任何奶牛的活动范围之外，且X>2B。

  • 对于此转移中的每个XX求F(X)F(X)都要便利区间[X−2B,X−2A][X-2B,X-2A],太慢

  • 所以快速找到此区间使得F(Y)F(Y)最小的元素是解题的关键。

    可以用堆来优化哦

  • 使用C++的STL中的priority_queue
  • 求F(X)F(X)时，我们维护一个小根堆，保证堆中包含所有的i∈[X−2B,X−2A]i\in [X-2B,X-2A]所对应的F(i)F(i)值，这样操作时间就从扫区间的O(N)O(N)级别变成了O(log2N)O(\log_2N)级别了
  • 求解XX对应的F(X)F(X)时，不允许堆中出现坐标大于X−2AX-2A的点，这样的点不能用来转移F(X)F(X)，又不能抛弃之，因为它可能对求后续点的FF值有用
  • 堆中可以出现坐标小于X−2BX-2B的点，若其出现在对头，则抛弃
  • 求出XX点的FF值后，将(X−2A+2,(F(X−2A+2)))(X-2A+2,(F(X-2A+2)))放入堆，为求F(X+2)F(X+2)作准备
  • 堆中点坐标皆为偶数

代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 1 << 31;
const int MAXL = 1000010;
const int MAXN = 1010;
int F[MAXL];
int cowThere[MAXL];//用于记录某点是否有奶牛出没
int n, l, a, b;
struct Fx {
    int x, f;
    bool operator<(const Fx &a) const {return f > a.f;}
    Fx(int xx = 0, int ff = 0): x(xx), f(ff) {}
};//优先队列用结构体
priority_queue<Fx> q;
int main () {
    cin >> n >> l;
    cin >> a >> b;
    a <<= 1; b <<= 1;//线性操作，所以先将半径处理成直径
    memset(cowThere, 0, sizeof(cowThere));
    for (int i = 0; i < n; i++) {
        int s, e;
        cin >> s >> e;
        cowThere[s + 1]++;
        cowThere[e]--;
    }
    int inCows = 0;
    for (int i = 0; i <= l; i++) {
        F[i] = INF;
        inCows += cowThere[i];
        cowThere[i] = inCows > 0;
    }//利用差分思想实现快速记录某点是否有奶牛出没
    for (int i = a; i <= b; i += 2) {
        if (!cowThere[i]) {
            F[i] = 1;
            if (i <= b + 2 - a) q.push(Fx(i, 1));//确保提前进堆的点可以用于首轮递推
        }
    }//首先初始化初始区间，为最开始的边界做准备
    for (int i = b + 2; i <= l; i += 2) {//dp()
        if (!cowThere[i]) {
            Fx fx;
            while (!q.empty()) {
                fx = q.top();
                if (fx.x < i - b) q.pop();//如果堆顶元素坐标小于X-2B，抛弃不用
                else break;
            }
            if (!q.empty()) F[i] = fx.f + 1;//如果堆空了，说明原来所有堆中元素全部不可用
        }
        if (F[i - a + 2] != INF) q.push(Fx(i - a + 2, F[i - a + 2]));
    }
    if (F[l] == INF) cout << -1 << endl;
    else cout << F[l] << endl;
    return 0;
}