自动搬运

查看原文

来自洛谷，原作者为

	kevinchw ←BJ高二普通学生

搬运于2025-08-24 22:43:31，当前版本为作者最后更新于2022-12-06 18:24:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

「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;
}