「DPOI-1」道路规划 题解

· · 题解

「DPOI-1」官方题解

题意

给你一个无向完全图，问你能不能把每条边定向，使得这张图变成一个有向无环图，而且第 i 个点的出度在 [l_i,r_i] 区间内。

思路

诈骗题。

由于 n 最大有 10^5，所以肯定不能把图建出来。通过有向无环图所以想到了拓扑排序。只要构造出来一个拓扑序，就可以建出唯一的有向无环图。而拓扑序中第 i 个点的出度就是比它编号大的点的个数，即 n-i。于是，这题就可以转化成：

给定 n 个区间 [l_i,r_i]，求是否存在一个 1\sim n 的排列 a，使得 \forall 1\leq i \leq n,l_i\le a_i\le r_i。

上面的题目就可以贪心求解。我们可以枚举 1\sim n 分别放进哪个区间里。

设当前搜到了 i，则把所有 l_i = i 的区间右端点加入小根堆。匹配时则取出堆中最小右端点把 i 放进对应区间。如果在操作过程中堆为空或最小右端点比 i 小，则不存在一种定向方案。

贪心策略的正确性怎么证明呢？现在我们假定在讨论 i 时我们选择了一个 r_x > r_{\min}，若有解，我们显然可以交换这两者，且仍然保持有解——因为此时 r_{\min} 放置的位置 j 满足 i < j \leq r_{\min} < r_x，这个位置对应 r_x, r_{\min} 而言均合法。于是选择 r_{\min} 不劣于选择其他 r_x。

代码

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define inf (int)2e9
#define ldb long double
#define db double
#define ft float
#define pb push_back
#define ins insert
#define myset(a,b,c,d) for(int i=b;i<=c;i++)a[i]=d;
using namespace std;

priority_queue<int,vector<int>,greater<int> > q;//小根堆
struct node
{
    int l,r;
}a[100005];
vector<int> v[100005];//储存右端点
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        q=priority_queue<int,vector<int>,greater<int> >();//清空
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            v[i].clear();
            int x;
            scanf("%d",&x);
            a[i].r=n-x;//计算右端点
        }
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            a[i].l=n-x;//计算左端点
            v[a[i].l].pb(a[i].r);//记录右端点
        }
        int now=1,op=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<(int)v[i].size();j++)q.push(v[i][j]);//右端点插入堆中
            if(q.empty())//堆为空
            {
                cout<<"NO\n";
                op=1;
                break;
            }
            int x=q.top();q.pop();
            if(x<i)//右端点不合法
            {
                cout<<"NO\n";
                op=1;
                break;
            }
        }
        if(!op)cout<<"YES\n";
    }
    return 0;
}