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

题意整理

• Alice和Bob在打牌，Alice有p1张石头牌，q1张剪刀牌，m1张布牌,Bob有p2张石头牌，q2张剪刀牌，m2张布牌。
• 每次Alice赢牌得一分，平局不得分不扣分，输牌扣一分。
• 如果Alice知道Bob每次出什么牌，问Alice怎样出牌，得分最多。

方法一（模拟）

1.解题思路

• 如果Bob出剪刀，Alice只有出石头才能获胜，所以Alice出石头获胜最多的次数为。
• 如果Bob出布，Alice只有出剪刀才能获胜，所以Alice出剪刀获胜最多的次数为。
• 如果Bob出石头，Alice只有出布才能获胜，所以Alice出布获胜最多的次数为。
• 获胜的次数为三者累加的结果。
• 然后减去获胜消耗的牌，计算剩下各有多少张牌。
• 利用类似的方式计算剩下的牌中最多有多少平局。
• 总牌数-获胜次数-平局即可得到至少输了多少局。
• 赢牌次数减去输牌次数即可得到最终的得分。

动图展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 
     * @param p1 int 
     * @param q1 int 
     * @param m1 int 
     * @param p2 int 
     * @param q2 int 
     * @param m2 int 
     * @return int
     */
    public int Highestscore (int n, int p1, int q1, int m1, int p2, int q2, int m2) {
        //Alice通过石头获胜的最大次数
        int a=Math.min(p1,q2);
        //Alice通过剪刀获胜的最大次数
        int b=Math.min(q1,m2);
        //Alice通过布获胜的最大次数
        int c=Math.min(m1,p2);
        //Alice和Bob手上剩余的牌
        p1-=a;q2-=a;q1-=b;
        m2-=b;m1-=c;p2-=c;
        //Alice赢牌的最大次数
        int sum1=a+b+c;
        //Alice通过剩下石头平局的最大次数
        int d=Math.min(p1,p2);
        //Alice通过剩下剪刀平局的最大次数
        int e=Math.min(m1,m2);
        //Alice通过剩下的布平局的最大次数
        int f=Math.min(q1,q2);
        //Alice剩下的牌平局的最大次数
        int sum2=d+e+f;
        //最大赢牌的得分减去最小输牌扣的分
        sum1-=(n-sum1-sum2);
        return sum1;
    }
}

3.复杂度分析

• 时间复杂度：需要执行常数次比较和加减运算，所以时间复杂度为。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为。