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

题目的主要信息：

• Alice的牌里有p1张石头牌，q1张剪刀牌，m1张布牌，Bob的牌里有p2张石头牌，q2张剪刀牌，m2张布牌，每人都是n张
• 赢一局得1分，输一局扣1分，平局不得分，问Alice在每次知道Bob出什么牌的情况，怎么出牌最终得分最高

方法一：暴力模拟

具体做法：
我们利用贪心的思想，Alice知道Bob每次出什么牌，如果她手里有可以赢的牌就出可以赢的牌去得分，如果没有再看有没有相同的牌争取平局不扣分，最后实在不行再出要输的牌扣分，这样得分才能最高。
因为三种牌是相互克制的，出牌顺序并不影响得分，因此我们可以按照Bob先出石头再出剪刀最后出布的顺序来模拟。

class Solution {
public:

    int Highestscore(int n, int p1, int q1, int m1, int p2, int q2, int m2) {
        int res = 0;
        //Alice赢的局
        while(p2 > 0){
            if(m1 > 0){ //Bob出石头，Alice有布出布，否则Bob的石头留到后面
                m1--;
                p2--;
                res++; //得分
            }
            else
                break;
        }
        while(q2 > 0){
            if(p1 > 0){ //Bob出剪刀，Alice有石头出石头，否则Bob的剪刀留到后面
                p1--;
                res++; //得分
                q2--;
            }
            else
                break;
        }
        while(m2 > 0){
            if(q1 > 0){ //Bob出布，Alice有剪刀出剪刀，否则Bob的布留到后面
                q1--;
                res++; //得分
                m2--;
            }
            else
                break;
        }
        //打平的局
        while(p2 > 0){
            if(p1 > 0){ //Bob出石头，Alice没有布了，有石头出石头，打平
                p1--;
                p2--;
            }
            else
                break;
        }
        while(q2 > 0){
            if(q1 > 0){ //Bob出剪刀，Alice没有石头了，有剪刀出剪刀，打平
                q1--;
                q2--;
            }
            else
                break;
        }
        while(m2 > 0){
            if(m1 > 0){ //Bob出布，Alice没有剪刀了，有布出布，打平
                m1--;
                m2--;
            }
            else
                break;
        }
        //Alice输的局：最后Bob还剩下的牌Alice都输
        while(p2 > 0){ 
            p2--;
            res--;
        }
        while(q2 > 0){
            q2--;
            res--;
        }
        while(m2 > 0){
            m2--;
            res--;
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，最坏情况遍历所有的牌，一共张
• 空间复杂度：，常数级空间

方法二：直接计算

具体做法：
上面的循环可以用min函数直接计算，比如Bob出石头Alice能赢的局就是双方的，同理其他的可以类似计算，这就是Alice能赢的局，得分加上局数就行了。后面他们手中各种牌要减去相应的局数（被消耗掉了），得到的牌用相同的手法处理平局的情况，最后Bob手中剩余的牌Alice都赢不了，得分减去这些牌数。

class Solution {
public:

    int Highestscore(int n, int p1, int q1, int m1, int p2, int q2, int m2) {
        int res = 0;
        int temp1 = min(p2, m1); //Bob出石头，Alice出布能赢的局
        int temp2 = min(q2, p1); //Bob出剪刀，Alice出石头能赢的局
        int temp3 = min(m2, q1); //Bob出布，Alice出剪刀能赢的局
        res = temp1 + temp2 + temp3; //上三种情况得分
        //减掉上面用掉的牌
        p2 -= temp1; 
        m1 -= temp1;
        q2 -= temp2;
        p1 -= temp2;
        m2 -= temp3;
        q1 -= temp3;
        temp1 = min(p1, p2); //Bob出石头，Alice出石头，打平的局
        temp2 = min(q1, q2); //Bob出剪刀，Alice出剪刀，打平的局
        temp3 = min(m1, m2); //Bob出布，Alice出布，打平的局
        //减掉上面用掉的牌
        p2 -= temp1;
        q2 -= temp2;
        m2 -= temp3;
        return res - p2 - q2 - m2; //最后剩余的Bob手中的牌都是Alice不能赢的
    }
};

复杂度分析：

• 时间复杂度：，直接计算，不含循环
• 空间复杂度：，常数级空间