题解：P8896 「DPOI-1」道路规划

· · 题解

题意简述

给定长度为 n 的序列 l 和 r，问是否存在一个任意两点之间都有边的 DAG，使得点 i 的出度属于区间 [l_i,r_i]。

Part 1

考虑这个 DAG 的拓扑序。由拓扑序的定义，每条边都必须由前面的节点指向后面的节点。又因为每两个点之间都有边，所以每个点的出度就等于拓扑序中在它之后的点数。

于是得到结论：对于每个 0 \le i < n，恰好有一个点的出度为 i。

Part 2

现在问题变为：给定 n 个区间，问能否将 0 到 n-1 这 n 个数与这些区间配对，使得每个数都属于与之配对的区间。

直接跑二分图最大匹配显然会超时，所以考虑贪心。

在所有包含 0 的区间中，显然将 r 最小的区间分配给 0 是最佳的。在剩下的包含 1 的区间中，如果某个区间的 r 值小于 1，直接 NO 即可（因为每个区间都要得到配对）。否则，继续将这些区间中 r 最小的区间分配给 1，如此类推。

于是得到做法：建立优先队列 q，在对 x 进行配对时，先往队列中插入所有满足 l_i=x 的区间的右端点，然后判断：如果队首小于 x，则输出 NO。否则，将其出队，继续循环。

“找 l_i=x 的区间”这一部分是显然的，排序+双指针即可做到 O(n)。所以总时间复杂度是 O(n \log n)。 ::::success[AC 代码]

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct node {
    int l,r;
    inline bool operator < (node n) {return l<n.l;}
}a[100001];
priority_queue<int,vector<int>,greater<int> > q;
int main() {
    int T,n,i,j;
    cin>>T;
    while(T--) {
        cin>>n;
        for(i=0;i<n;i++) cin>>a[i].l;
        for(i=0;i<n;i++) cin>>a[i].r;
        sort(a,a+n);
        j=0;
        for(i=0;i<n;i++) {
            while(j<n && a[j].l<=i) q.push(a[j++].r);
            if(q.empty() || q.top()<i) break;
            q.pop();
        }
        while(!q.empty()) q.pop();
        if(i==n) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

:::: AC 记录。