问题描述

解题分析

程序实现

# include<iostream>
# include<cstring>
# include<queue>
using namespace std;

const int INFINITE = 1 << 31;
const int MAXL = 1000001;
const int MAXN = 10001;

int l, n, s, e, a, b;

struct id_f
{
    int id;
    int f;
    id_f(int ii, int ff)
    {
        id = ii;
        f = ff;
    }
};

bool operator < (const id_f idf1, const id_f idf2)//在优先级队列里,f值越小的越优先
{
    return idf1.f > idf2.f;
}

int main()
{
    cin >> n >> l;
    cin >> a >> b;
    a <<= 1;//a,b的定义变为覆盖的直径
    b <<= 1;
    int cowsHere[l + 1];
    memset(cowsHere, 0, sizeof(cowsHere));
    for(int i = 0; i < n; i++)
        {
            cin >> s >> e;
            while(s < e)
                {
                    s++;
                    cowsHere[s]++;
                }
            cowsHere[e]--;
        }
    int f[l + 1];
    memset(f, INFINITE, sizeof(f));
    priority_queue<id_f> pq;
    for(int i = a; i < b + 1; i += 2)
        {
            if(cowsHere[i] == 0)
                {
                    f[i] = 1;
                    if(i <= b + 2 - a)
                        pq.push(id_f(i, f[i]));
                }
        }
    for(int i = b + 2; i < l + 1; i += 2)
        {
            if(!pq.empty())
                {
                    id_f ele = pq.top();
                    while(ele.id < i - b)
                        {
                            pq.pop();
                            if(pq.empty())
                                break;
                            ele = pq.top();
                        }
                    if(!pq.empty() and cowsHere[i] == 0) f[i] = ele.f + 1;
                }
            if(f[i + 2 - a] != INFINITE)
                pq.push(id_f(i + 2 - a, f[i + 2 - a]));
        }
    if(f[l] != INFINITE) cout << f[l] << endl;
    else cout << -1 << endl;

    return 0;
}//时间复杂度：O(nlogn)

运行结果