本文涉及知识点

C++贪心

「DPOI-1」道路规划

题目背景

不可以，总司令。

题目描述

战场上有 $n$ 个据点，从 $1\sim n$ 编号。每两个据点之间都有一条双向道路。

一天，总司令来战区巡视，走着走着迷路了，于是愤怒地下达命令，让你把每一条双向道路变成单向的，使得这些道路不包含环（否则总司令会迷路）。但由于每个据点的规模互不相同，总司令从第 $i$ 个据点出发沿着单向道路能直接到达的据点数量需要在 $[l_i,r_i]$ 之间。换言之，第 $i$ 个点的出度需要在 $[l_i,r_i]$ 之间。你需要告诉总司令有没有可能满足他的需求。

输入格式

本题有多组测试数据。

第一行，一个整数 $T$，表示数据组数。

对于每组数据：

第一行，一个整数 $n$，表示据点数量；

第二行，$n$ 个整数 $l_1,l_2,\dots ,l_n$；

第三行，$n$ 个整数 $r_1,r_2,\dots ,r_n$。

输出格式

对于每组数据：

一行，一个字符串。若可以满足总司令的需求，一行 YES；否则，一行 NO。

样例 #1

样例输入 #1

2
5
0 1 4 0 0
3 4 4 1 3
3
1 2 2
2 2 2

样例输出 #1

YES
NO

样例 #2

样例输入 #2

见下发文件 road2.in

样例输出 #2

见下发文件 road2.out

提示

样例 #1 解释

下面是第 $1$ 组数据中一种可行的方案：

样例 #2 解释

该样例满足测试点 $3\sim 6$ 的限制。

数据范围

本题测试点分数不等分。

测试点编号	$n\le$	特殊条件	每个测试点分数
$1\sim 2$	$10$	无	$5$
$3\sim 6$	$1000$	无	$5$
$7\sim 8$	$10^5$	所有 $l_i=i-1$ 或所有 $l_i\ge \min (i,n-1)$	$5$
$9\sim 10$	$10^5$	$l_i=0$ 或 $r_i=n-1$	$5$
$11\sim 15$	$10^5$	无	$10$

对于 $100\%$ 的数据，$1\le n\le 10^5$，$0\le l_i\le r_i<n$，$1\le T\le 10$。

错误解法

由于只要求无环，不要求连通，故出边尽可能得少。忽略最大出边。
如果无环，一定能求拓扑序。
最小出边lefts升序排序，如果a[i]全部小于等于i。则有解。出边多的指向出边少的。
否则无解。a[i1] < i1.$\to$ i >= i1，至少有一条边指向a[0…i1-1]之外，这种情况要么有环，要么是无限点。
错误原因：只能将双向图改成单向图，不能删除边。

贪心

由于两两连接，故任何据点出度入度之和一定为n。
由于没有环，一定有一个据点，出度为0，即所有节点都指向它。
一定有一个据点出度为1，除指向节点0外，被其它所有节点指向。
$⋮$
第i个节点，出度为i，指向已处理的节点，被未处理的节点处理。

如果有多个据点可以选择，选择r小的。用小根堆hr，记录所有li <=i 的ri。

2025年11月19号补充

性质一:任意点出度入度之后是N-1。
性质二：有且仅有一个点是出度为i,i$\in [0,N-1]$，出度为i的点指向出度$0\sim i-1$的点，被其它点指向 。
性质二一：无环故有点出度为0的点。如果有两个点u、v 出度为0，则u、v都被所有点指向，包括v、u。和假设矛盾。
性质二二：如果i == n-1符合性质二，则i=n也符合性质二。假定u和v的出度都为n，他们都指向$0\sim n-1$,也就是不会指向其它点，其它点都指向uv。即uv相互指向，和假设矛盾。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>

#include <bitset>
using namespace std;



template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {
	vector<T> ret(n);
	for(int i=0;i<n;i++) {
		scanf(pFormat, &ret[i]);	
	}
	return ret;
}

template<class T = int>
vector<T> Read( const char* pFormat = "%d") {
	int n;
	scanf("%d", &n);
	vector<T> ret;
	T d;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

string ReadChar(int n) {
	string str;
	char ch;
	while (n--) {
		do
		{
			scanf("%c", &ch);
		} while (('\n' == ch));
			str += ch;
	}
	return str;
}

class Solution {
public:
	bool Ans(vector<int>& mins, vector<int>& maxs)
	{
		const int N = mins.size();
		vector<pair<int, int>> lr;
		for (int i = 0; i < N; i++) {
			lr.emplace_back(mins[i], maxs[i]);
		}
		sort(lr.begin(), lr.end(), greater<>());
		multiset<int> sr;
		for (int i = 0; i < N; i++) {
			while (lr.size() && (lr.back().first <= i)) {
				sr.emplace(lr.back().second);
				lr.pop_back();
			}
			if (sr.empty() || (*sr.begin() < i)) { return false; }
			sr.erase(sr.begin());
		}
		return true;
	}
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG
	int T,n;
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d", &n);
		auto left = Read<int>(n);
		auto r = Read<int>(n);
		auto res = Solution().Ans(left,r);
		cout <<(res?"YES":"NO") << std::endl;
	}
#ifdef _DEBUG
	//Out(abcd, "abcd=");
#endif	
	
	return 0;
}

单元测试

vector<int>left, r;
		TEST_METHOD(TestMethod11)
		{
			left = { 0,1,4,0,0 }, r = { 3,4,4,1,3 };
			auto res = Solution().Ans(left, r);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod12)
		{
			left = { 1,2,2 }, r = { 2,2,2 };
			auto res = Solution().Ans(left, r);
			AssertEx(false, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。