[puzzle]二进制游戏 - 魔法数
发表于 : 2019年03月31日 17:12
原题描述:
1. 整个范围内,只要是相邻且值不同的元素,都可以调换,不分为左半部份/右半部分。
2. 后一次调换基于上一次的结果:
例如 1 0 0 0 0 1,可以调换 1 0 (#a),也可以调换 0 1 (#b),若执行了 #a,
得到 0 1 0 0 0 1,那么这次可能的调换位置是(1,2) (2,3) (5,6) (为了直观,这里的位置从1开始算
实现算法后,可以考虑数量较大的情况,比如 100 位,1000 位。
Kira在玩一个二进制游戏,她需要找魔法数,就是如果当一个数字(确保是偶数位)从中间切开来,两边的“魔法对”是一样对的。
魔法对是当 a[n] = 1 and a[m] = 0 并且 n < m
比如说 00100 就有2个魔法对
Kira每次可以互换相邻的两个0和1,现在请帮Kira计算出要最少互换多少次才能让一个数字变成魔法数
以上是一个网友问的问题,沟通后我弄清楚了一些细节,补充一下:比如说,
1 1 0 1 0 0 1 0
当互换第六位和第七位的时候,1 1 0 1和 0 1 0 0 都有2个魔法对
输入格式是
n(多少位,确保是偶数的)
数字(比如说是0 1 1 0)
1. 整个范围内,只要是相邻且值不同的元素,都可以调换,不分为左半部份/右半部分。
2. 后一次调换基于上一次的结果:
例如 1 0 0 0 0 1,可以调换 1 0 (#a),也可以调换 0 1 (#b),若执行了 #a,
得到 0 1 0 0 0 1,那么这次可能的调换位置是(1,2) (2,3) (5,6) (为了直观,这里的位置从1开始算
实现算法后,可以考虑数量较大的情况,比如 100 位,1000 位。