CF1373F Network Coverage

2021-01-29 18:17

阅读：569

标签：bool cpp struct turn name 变量 code 限制链接

题目链接

对于每一个 \(i\) 可以看作一个管道。赋予三个信息：

\(\text{minIn}_i\) 表示至少要从上一家 \(i - 1\) 得到连接数，才能正常供给 \(i\) 城市
\(\text{minOut}_i\) 最坏情况下最少给下一家 \(i + 1\) 多少连接数
\(\text{maxOut}_i\) 表示最多能给下一家 \(i + 1\) 多少连接数

三个变量维护完毕，我们发现我们可以通过某种方法合并两个相邻的管道，最后剩下一个管道，只需自检查 \(\text{minIn} \le \text{minOut}\) 即可（在最低限度下自我循环传输）。

合并需要分类讨论，假如合并 \(x, y\)。

首先必须满足 \(x.maxOut \ge y.minIn\)，不然无论何时都满足不了。
如果 \(x.minOut \le y.minIn\)，那么合并后的最低需求会变大，最大输出量也会被 \(x.maxOut\) 而限制
否则，最低输出量会被提高（或不变），最大输出量同样受到限制。

#include 
#include 

using namespace std;

const int N = 1000005;

int n, a[N], b[N];

struct Pipe{
	int minIn, minOut, maxOut;
};

Pipe get(int x, int y) {
	if (x

CF1373F Network Coverage

标签：bool cpp struct turn name 变量 code 限制链接

原文地址：https://www.cnblogs.com/dmoransky/p/13200527.html

上一篇：Linux下Apache服务的查看和启动

下一篇：C# - 双缓冲绘图技术

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：CF1373F Network Coverage
文章链接：http://soscw.com/essay/48806.html

亲，登录后才可以留言！

CF1373F Network Coverage

评论

热门文章

推荐文章

最新文章

置顶文章