题目链接：[ POJ - 2373 ]

题目大意

有一个直线的山脊，喷泉是一个在中间向两边同时喷的，最近喷a，最远b。同时山脊上有牛，每只牛在一个区域里活动，牛活动的区域只能被一个喷泉的水来覆盖。求最少的喷泉使山脊上所有地方都能有水浇灌到

思路

手工实现优先队列的方法

如果一个队列满足以下条件:

  1. 开始为空
  2. 每在队尾加入一个元素a之前，都从现有队尾往前删除元素 ，一直删到碰到小于a的元素为止，然后再加入a,那么队列就是递增的，当然队头的元素，一定是队列中最小的

题解代码

#include<bits/stdc++.h>
using namespace std;
const int INFINITE = 1<<30;
const int MAXL = 1000010;
const int MAXN = 1010;

int F[MAXL]; // F[L]就是答案
int cowThere[MAXL]; //cowThere[i]为1表示点i有奶牛
int N,L,A,B;

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(void)
{
    cin >> N >> L;
    cin >> A >> B;
    A <<= 1;
    B <<= 1; //A,B的定义变为覆盖的直径
    memset(cowThere,0,sizeof(cowThere));
    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 ++) { //算出每个点是否有奶牛
        F[i] = INFINITE;
        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 )
            //在求F[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())
                F[i] = fx.f + 1;
        }

        if( F[i- A + 2] != INFINITE) {
            //队列中增加一个+1可达下个点的点
            qFx.push(Fx(i- A + 2, F[i- A + 2]));
        }
    }

    if( F[L] == INFINITE )
        cout << -1 <<endl;
    else
        cout << F[L] << endl;

    return 0;
} // 复杂度:O(nlogn)