RainAir
My OI Blog
RainAir
「二分图模板」距离序列

题目描述

已知序列 $S={0,1,\cdots ,n-1}$,序列里有 $n$ 个数,从 $0$ 到 $n-1$。定义两个数 $x,y$ 的距离 $D(x,y) = min{|x-y|,N-|x-y|}$.
定义序列 S 的一个排列 T ,那么这两个序列的距离序列 $Q(S,T) = {D(S_0,T_0),D(S_1,T_1),\cdots,D(S_{n-1},T_{n-1}}$
现在知道距离序列,求出可能的 $T$ 中字典序最小的那个。
其中 $n \leq 10^4$。

题解

我们首先考虑建出一张二分图 $G$,边 $x,y$ 存在的意义是 $T$ 的第 $x$ 个元素可以放置 $y$.
那么我们建完这张二分图后,如果最大匹配数为 $n$,那么就存在解。
我们考虑如何输出字典序最小的解。
具体来说记录每个点匹配到了哪个点,每次优先遍历编号大的点,这样最后得到的序列就是字典序最小的了。
时间复杂度 $O(n^2)$

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/310
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「二分图模板」距离序列
题目描述 已知序列 $S={0,1,\cdots ,n-1}$,序列里有 $n$ 个数,从 $0$ 到 $n-1$。定义两个数 $x,y$ 的距离 $D(x,y) = min{|x-y|,N-|x-y|}$. 定义序列 S 的一个排列 …
扫描二维码继续阅读
2018-11-27
标签
近期评论