[puzzle]二进制游戏 - 魔法数

回复
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

[puzzle]二进制游戏 - 魔法数

帖子 523066680 »

原题描述:
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 位。
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

Re: [puzzle]二进制游戏 - 魔法数

帖子 523066680 »

关于计算两侧的"魔法对"的数量,

一开始我用的是很无脑的方案,两层 for 遍历,

代码: 全选

int count_pair1(vector<int> &arr, int begin, int end )
{
    register int pair = 0;
    register int L, R;
    for (L = begin; L < end; L++)
        for (R = L+1; R <= end; R++)
            if ( arr[L] > arr[R] )
                pair++;
    return pair;
}
测试数据稍微增加就卡的不行,在优化的时候发现这段写的太差,累计的过程有点像动态规划,可以从右到左叠加0的个数来统计
于是改成了

代码: 全选

int count_pair2(vector<int> &arr, int begin, int end )
{
    register int zero = 0, pair = 0;
    for (register int id = end; id >= begin; id--)
        arr[id] == 0 ? zero++ : pair += zero;
    return pair;
}
测试代码:
#include <iostream>
#include <string>
#include <vector>

using namespace std;
int count_pair1(vector<int> &arr, int offset, int len );
int count_pair2(vector<int> &arr, int offset, int len );

int main(int argc, char *argv[] )
{
vector<int> arr{1,1,1,0,0, 0,1,1,0,0};
//arr = {1,1,0,1,0,1, 0,0,1,0,0,0};
int len = arr.size();
cout << count_pair1( arr, 0, len-1 ) << endl;
cout << count_pair2( arr, 0, len-1 ) << endl;

int L = count_pair2( arr, 0, len/2-1 );
int R = count_pair2( arr, len/2, len-1 );
cout << L << ", " << R << endl;

return 0;
}

int count_pair2(vector<int> &arr, int begin, int end )
{
register int zero = 0, pair = 0;
for (register int id = end; id >= begin; id--)
arr[id] == 0 ? zero++ : pair += zero;
return pair;
}

int count_pair1(vector<int> &arr, int begin, int end )
{
register int pair = 0;
register int L, R;
for (L = begin; L < end; L++)
for (R = L+1; R <= end; R++)
if ( arr[L] > arr[R] )
pair++;
return pair;
}
头像
rubyish2
初来炸道
初来炸道
帖子: 4
注册时间: 2019年04月28日 15:18
联系:

Re: [puzzle]二进制游戏 - 魔法数

帖子 rubyish2 »

完全看不懂※這一題
@_
回复

在线用户

正浏览此版面之用户: 没有注册用户 和 0 访客