牛牛和牛妹的取球游戏题解

牛牛和牛妹在玩一个取球游戏，有若干个球放置在一个竖直透明的圆柱体中，圆柱体的横截面积恰好与每个球的横截面积相同。这些球只有两种颜色，一种是红色，一种是黑色。
轮到每个人的回合时，每次可以取出其中的两个球，但是需要满足每次取出时只能拿走相邻的两个不同颜色的球。因为这两个球被取出，其他球可能会由于重力的作用而下落。
每次游戏牛牛都是先手，而牛妹是后手。两人交替取球，如果轮到某个人在自己的回合内无法取球，那么判定那个人输。牛牛和牛妹都不想输，所以他们每一步都会采取最优策略。
为了简化该问题，给定你一串由R和B组成的字符串，分别代表红球和黑球，字符串的排列顺序与圆柱体从下往上的排列一致，请你写一个程序，来判定谁会获得胜利，如果牛牛获得胜利，返回"niuniu"，反之，返回"niumei"。

我们可以将这个问题简化成，每次从一个只含有'R'和'B'的字符串中删除'RB'或'BR',如果一个人在他的回合内无法进行删除，那么他就输了。
我们可以对多种情况进行模拟，试图寻找一个规律：
RRBB->RB->"" 牛妹赢
BBBB 牛妹赢
BBRBBBBBRR->BBBBBBRR->BBBBBR->BBBB 牛牛赢
我们不难发现，无论怎么删除，我们可以发现删除次数是不会变的，删除的次数由B的数量和R的数量中的最小值决定。
该例子中（BBRBBBBBRR->BBBBBBRR->BBBBBR->BBBB 牛牛赢 ），R的数量是3，B的数量是7，所以删除的次数最多为3，所以我们只需要统计删除的次数的奇偶性就可以判断是谁胜利了。
将上述思路，使用代码模拟如下：
时间复杂度
空间复杂度

class Solution {
public:
    /**
     * 如果牛牛获得胜利，返回"niuniu"，反之，返回"niumei"。
     * @param s string字符串 一串由R和B组成的字符串，分别代表红球和黑球，字符串的排列顺序与圆柱体从下往上的排列一致
     * @return string字符串
     */
    string solve(string s)
    {
        // write code here
        int n, tot, i;
        int cnt[2];
        n = s.size(), cnt[0] = cnt[1] = 0;
        for (i = 0; i < n; i++)
            if (s[i] == 'R')
                cnt[0]++;
            else if (s[i] == 'B')
                cnt[1]++;
        cnt[0] > cnt[1] ? tot = cnt[1] : tot = cnt[0];
        if (tot % 2)
            return "niuniu";
        return "niumei";
    }
};