题面
题意
给定一个序列，求一个相邻位奇偶不同、且移动步数最少、字典序最小的方案。
样例
Input:
5 5 3 1 4 2
Output:
5 2 1 4 3
先不管字典序，把每个点插到它应该到的地方，是可以的。
考虑让字典序变小，同时代价不变。
把每个点按移动方向：向左、向右、不动分类。
如果是同一类，交换两条路径，总代价是不变的（红与蓝对比）
而如果不是同一类，交换后就会有交叉（橙色部分），所以类之间相互独立
然后最后整个路径图就会是这样
代码
咕了
题面
题意
给定一个序列，求一个相邻位奇偶不同、且移动步数最少、字典序最小的方案。
样例
Input:
5 5 3 1 4 2
Output:
5 2 1 4 3
先不管字典序，把每个点插到它应该到的地方，是可以的。
考虑让字典序变小，同时代价不变。
把每个点按移动方向：向左、向右、不动分类。
如果是同一类，交换两条路径，总代价是不变的（红与蓝对比）
而如果不是同一类，交换后就会有交叉（橙色部分），所以类之间相互独立
然后最后整个路径图就会是这样
代码
咕了