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

头像
523066680
Administrator
Administrator
帖子: 481
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 53 times
Been thanked: 93 times
联系:

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

帖子 #1 523066680 » 2019年03月31日 17:12

原题描述:
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
帖子: 481
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 53 times
Been thanked: 93 times
联系:

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

帖子 #2 523066680 » 2019年03月31日 20:42

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

一开始我用的是很无脑的方案,两层 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;
}


测试代码:
Code: [全选] [展开/折叠] [Download] (Untitled.cpp)
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5. using namespace std;
  6. int count_pair1(vector<int> &arr, int offset, int len );
  7. int count_pair2(vector<int> &arr, int offset, int len );
  8.  
  9. int main(int argc, char *argv[] )
  10. {
  11.     vector<int> arr{1,1,1,0,0, 0,1,1,0,0};
  12.     //arr = {1,1,0,1,0,1, 0,0,1,0,0,0};
  13.     int len = arr.size();
  14.     cout << count_pair1( arr, 0, len-1 ) << endl;
  15.     cout << count_pair2( arr, 0, len-1 ) << endl;
  16.  
  17.     int L = count_pair2( arr, 0, len/2-1 );
  18.     int R = count_pair2( arr, len/2, len-1 );
  19.     cout << L << ", " << R << endl;
  20.  
  21.     return 0;
  22. }
  23.  
  24. int count_pair2(vector<int> &arr, int begin, int end )
  25. {
  26.     register int zero = 0, pair = 0;
  27.     for (register int id = end; id >= begin; id--)
  28.         arr[id] == 0 ? zero++ : pair += zero;
  29.     return pair;
  30. }
  31.  
  32. int count_pair1(vector<int> &arr, int begin, int end )
  33. {
  34.     register int pair = 0;
  35.     register int L, R;
  36.     for (L = begin; L < end; L++)
  37.         for (R = L+1; R <= end; R++)
  38.             if ( arr[L] > arr[R] )
  39.                 pair++;
  40.     return pair;
  41. }

头像
rubyish2
初来炸道
初来炸道
帖子: 4
注册时间: 2019年04月28日 15:18
拥有现金: 锁定
Has thanked: 4 times
Been thanked: 1 time
联系:

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

帖子 #3 rubyish2 » 2019年04月29日 16:29

完全看不懂※這一題
@_


回到 “算法和编码”

在线用户

用户浏览此论坛: 没有注册用户 和 0 访客