#BZOJ4139. 金币换位问题
-
ID: 2722
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
金币换位问题
No submission language available for this problem.
题目描述
给定一个n，最开始序列长这样：
1111...10000...0__
n个1，n个0，两个空格
现在要求用最少的交换步数，使得最终的序列为
1010...1010__
就是前2n个都是10交替
所谓交换是指将相邻两个非空格的数一起挪到两个空格上。例如，下面是n=4时的一组合法解
11110000__
__11000011
101__00011
1010100__1
10101__001
10101010__
输入格式
输入一个n
输出格式
第一行输出最少移动步数
接下来一行为移动方案，只要输出被移动的两个非空格格子左边那个的编号。换不换行无所谓。详见样例。
4
5
1 4 8 6 9
数据范围与约定
对于100%的数据，2<n<=200000