题目名称	409. [NOI 2009]变换序列
输入输出	`transform.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	cqw 于2010-03-12加入
开放分组	全部用户
提交状态
分类标签	NOI 二分图贪心
	分享题解

通过：62，提交：143，通过率：43.36%
Troywar	100	0.000 s	0.00 MiB	C++
Youngsc	100	0.000 s	0.00 MiB	C++
LGLJ	100	0.009 s	1.83 MiB	C++
FoolMike	100	0.012 s	0.52 MiB	C++
AAAAAAAAAA	100	0.012 s	0.52 MiB	C++
thomount	100	0.014 s	0.67 MiB	C++
ztx	100	0.014 s	0.67 MiB	C++
fye	100	0.014 s	0.77 MiB	C++
Owaski	100	0.016 s	1.88 MiB	C++
ZXCVBNM_1	100	0.017 s	0.54 MiB	C++

关于变换序列的近10条评论(全部评论)
回复 @QhelDIV : 字典序最小。核糖核酸 2017-02-03 20:42 7楼
感谢BYV学长的题解，我终于看懂了贪心匹配求字典序最小匹配！ FoolMike 2016-11-29 21:04 6楼
水题调好久，不活了TAT 天一阁 2015-06-16 11:14 5楼
为了过7个点代码写了3天我容易么…… 苏轼 2013-06-25 10:42 4楼
这题可以枚举……因为一个T至多对应两个值，确定一个后排除之即可二分图匹配神马的人家才不会呢= = cstdio 2013-05-19 18:39 3楼
为什么Dinic会错呢 QhelDIV 2013-05-15 11:44 2楼
gsfgdsf 苏轼 2011-10-19 20:43 1楼

409. [NOI 2009]变换序列

★★★ 输入文件：transform.in 输出文件：transform.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

对于$N$个整数$0,1,\cdots,N-1$一个变换序列$T$可以将$i$变成$T_i$，其中$T_i \in \{0,1,\cdots,N-1\}$且$\bigcup_{i=0}^{N-1}\{T_i\}=\{0,1,\cdots,N-1\}$。

$\forall x,y\in\{0,1,\cdots,N-1\}$定义x和y之间的距离$D(x,y)=\min\{|x-y|, N-|x-y|\}$。给定每个i和T_i之间的距离D(i,T_i)，

你需要求出一个满足要求的变换序列T。如果有多个满足条件的序列，输出其中字典序最小的一个。

说明：对于两个变换序列S和T，如果存在p<N，满足对于i=0,1,……p-1，S_i=T_i且S_p<T_p，我们称S比T字典序小。

【输入文件】

输入文件transform.in

第一行包含一个整数N，表示序列的长度。

接下来的一行包含N个整数D_i，其中D_i表示i和T_i之间的距离。

【输出文件】

输出文件为transform.out。

如果至少存在一个满足要求的变换序列T，则输出文件中包含一行N个整数，表示你计算得到的字典序最小的T；

否则输出”No Answer”（不含引号）。

注意：输出文件中相邻两个数之间用一个空格分开，行末不包含多余空格。

【输入样例】

5

1 1 2 2 1

【输出样例】

1 2 4 0 3

【数据规模和约定】

20%的数据中N≤50；

60%的数据中N≤500；

100%的数据中N≤10000。