题意:

Alice有张石头牌、张剪刀牌、张布牌,
Bob有张石头牌、张剪刀牌、张布牌,
其中获胜得1分,平局不得分也不扣分,失败扣1分。
你可以随意安排出牌策略,问Alice最多可以得多少分?(可能是负数)

解法一(暴力模拟)

我们按照『能获胜就获胜,不能获胜就平局,实在不行才失败』这样一个贪心策略来,显然这样得分一定是最高的。
一. 我们首先考虑获胜的情况
    1. Alice出石头,Bob出剪刀。
    2. Alice出剪刀,Bob出布。
    3. Alice出布,Bob出石头。
    故当都不为0时,我们每次让同时减一,然后答案加一。
    当都不为0时,我们每次让同时减一,然后答案加一。
    当都不为0时,我们每次让同时减一,然后答案加一。
二. 我们接着考虑平局的情况
    1. Alice出石头,Bob出石头。
    2. Alice出剪刀,Bob出剪刀。
    3. Alice出布,Bob出布。
    故当都不为0时,我们每次让同时减一。
    当都不为0时,我们每次让同时减一。
    当都不为0时,我们每次让同时减一。
三. 最后考虑失败的情况
    由于只有获胜、平局、失败三种情况,其中获胜和平局两种情况的牌在前面已经出完了,故Alice剩下出的牌一定是失败的。
    故答案减即可。
代码:
class Solution {
public:
    int Highestscore(int n, int p1, int q1, int m1, int p2, int q2, int m2) {
        int ans=0;
        //胜利的
        while(p1>0&&q2>0){//石头胜剪刀
            ans++;//答案+1
            p1--,q2--;//两个牌的数量分别减一
        }
        while(q1>0&&m2>0){//剪刀胜布
            ans++;//答案+1
            q1--,m2--;
        }
        while(m1>0&&p2>0){//布胜石头
            ans++;
            m1--,p2--;
        }
        //平局的
        while(p1>0&&p2>0){//石头对石头
            p1--,p2--;
        }
        while(q1>0&&q2>0){//剪刀对剪刀
            q1--,q2--;
        }
        while(m1>0&&m2>0){//布对布
            m1--,m2--;
        }
        //失败的
        //Alice出剩下的牌一定会失败,故直接减去即可
        ans-=p1+q1+m1;
        return ans;
    }
};
时间复杂度:,最坏情况Alice出的所有牌都要在while循环中完成,总共有张牌,故时间复杂度为
空间复杂度:,程序中没有申请额外的空间,故空间复杂度为

解法二(直接计算)

我们首先考虑Alice获胜的情况:
    假设Alice出石头,Bob出剪刀
    1.
        
        显然这种情况获胜次数为,得分为
    2.
        
        显然这种情况获胜次数为,得分也为
    3.
        
        显然这种情况获胜次数为,得分也为
    综上所述,这种情况的得分为
    其他两种获胜的情况同理,得分分别为
我们接下来在考虑平局和失败两种情况时,首先应该将Alice和Bob消耗的牌数量给减掉,即:
    减去
    减去
    减去
我们接下来考虑平局的情况:
    1. Alice出石头,Bob出石头:显然平局次数为
    2. Alice出剪刀,Bob出剪刀:显然平局次数为
    3. Alice出布,Bob出布:显然平局次数为
接下来将平局情况消耗的牌数量减掉,即:
    减去
    减去
    减去
最后失败的情况同解法一,即答案减去即可
代码:
class Solution {
public:
    int Highestscore(int n, int p1, int q1, int m1, int p2, int q2, int m2) {
        int ans=0;//最后得分
        int t=min(p1,q2);//石头对剪刀
        ans+=t;//获胜次数
        p1-=t,q2-=t;//减去获胜消耗的牌
        t=min(q1,m2);//剪刀对布
        ans+=t;//获胜次数
        q1-=t,m2-=t;//减去获胜消耗的牌
        t=min(m1,p2);//布对石头
        ans+=t;//获胜次数
        m1-=t,p2-=t;//减去获胜消耗的牌
        t=min(p1,p2);//石头对石头
        p1-=t,p2-=t;//减去平局消耗的牌
        t=min(q1,q2);//剪刀对剪刀
        q1-=t,q2-=t;//减去平局消耗的牌
        t=min(m1,m2);//布对布
        m1-=t,m2-=t;//减去平局消耗的牌
        ans-=p1+q1+m1;//最后出的牌一定是失败的,答案减去牌的数量即可
        return ans;
    }
};
时间复杂度:,min函数的时间复杂度是的,程序只调用了级别次数min函数和级别次加减法运算,故总的时间复杂度为
空间复杂度:,程序没有申请额外的空间,故空间复杂度为