题解 | #石头、剪刀、布I#

题目的主要信息：

• Alice的牌里有p1张石头牌，q1张剪刀牌，m1张布牌，Bob的牌里有p2张石头牌，q2张剪刀牌，m2张布牌，每人都是n张
• Alice直到Bob每次出什么牌的情况下如何出牌可以使Alice赢的局数最多，输出最多次数

方法一：暴力模拟

具体做法：
因为剪刀石头布是相互克制的，你出一张牌，只要我有，必定能克制你的牌，因此出牌顺序是不影响赢的局数的，所以我们不妨假设Bob先出石头，再出剪刀，最后出布，每种牌都出完为止再出其他的牌。
对于Bob出的一种牌，我们检查Alice手中还有无可以克制它的牌，如果有，双方手中的出的牌各自减1，Alice赢一局，如果没有剩余克制它的牌了，对于Alice而言，Bob的这种牌他都不可能赢，不必再考虑了。三种牌都遍历结束即可找到最大胜利局数。

class Solution {
public:
    int Mostvictories(int n, int p1, int q1, int m1, int p2, int q2, int m2) {
        int res = 0;
        while(p2 > 0){ 
            p2--;  //Bob出石头
            if(m1 > 0){ //Alice还有布，就出布
                res++; //布赢石头
                m1--;  //布牌少1
            }else  //Alice没有布都是输
                break;
        }
        while(q2 > 0){
            q2--; //Bob出剪刀
            if(p1 > 0){ //Alice还有石头，就出石头
                res++; //石头赢剪刀
                p1--; //石头牌少1
            }else //Alice没有石头，都是输
                break;
        }
        while(m2 > 0){
            m2--; //Bob出布
            if(q1 > 0){ //Alice还有剪刀就出剪刀
                res++; //剪刀赢布
                q1--; //剪刀牌少1
            }else //Alice没有剪刀，都是输
                break;
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，最坏情况是张牌每张都过一遍
• 空间复杂度：，常数级变量

方法二：直接计算

具体做法：
仔细看方法一的循环，其实就是把双方手中相互克制的牌取最小值给Alice都算胜利，那我们可以用min函数直接计算相加。

class Solution {
public:
    int Mostvictories(int n, int p1, int q1, int m1, int p2, int q2, int m2) {
        return min(p1, q2) + min(q1, m2) + min(m1, p2); //直接每个取最小值就是赢的最多次数
    }
};

复杂度分析：

• 时间复杂度：，直接计算，常数空间
• 空间复杂度：，无额外空间使用