题解 | #三色球#

思路：

题目的主要信息：

• 1红球+1黄球+1蓝球=1彩票
• 1红球=2黄球+1蓝球
• 1黄球=2蓝球+1红球
• 1蓝球=2红球+1黄球

球的相互兑换是循环的，要求最多可兑换的彩票数

方法一：过程模拟+贪心
具体做法：
采用贪心思想，因为球换球不划算，所以先把能兑换彩票的球换完，再考虑球换球。
在abc不为0的情况下，每个参数减1，彩票数加1。一旦有一个数（假设是a)为0，用另外两个数来换球，这种时候需要3个b球+2个c球才能换一张彩票，最后换到只剩一种颜色的球为止。。因为是一个循环，所以不管是哪个球先被耗尽，另外两个球都能表示。

class Solution {
public:
    int two_color_ball(int x, int y){ //用两种球换另一种球，并加上两种球本身换彩排
        int count = 0;
        while(x > 0 && y > 0){
            x -= 3;
            y -= 2;
            if(x >= 0 && y >= 0)
                count++;
        }
        return count;
    }
    int solve(int a, int b, int c) {
        int res = 0;
        while(a > 0 && b > 0 && c > 0){ //优先换完
            a--;
            b--;
            c--;
            res++;
        }
        if(a == 0){ //红球没有换红球
            res += two_color_ball(b, c);
        }else if(b == 0){//黄球没有换黄球
            res += two_color_ball(c, a);
        }else {//蓝球没有换蓝球
            res += two_color_ball(a, b);
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，最多不超过这个复杂度，精确复杂度不可求
• 空间复杂度：，无额外空间

方法二：数学+贪心
具体做法：
上述模拟过程可以直接用数学来表现：第一个循环，可以直接找到abc三者最小值，可以直接都减去这个最小值，取到最小的那个为0.
再来看谁是0，另外两种球，一种是除以3，一种是除以2，找最小次数。

class Solution {
public:
    int solve(int a, int b, int c) {
        int res = min(a, min(b, c)); //取三者最小
        a -= res;
        b -= res;
        c -= res;
        if(a == 0)  //一种为0，用另外两种来换
            return res + min(b / 3, c / 2);
        else if(b == 0)
            return res + min(c / 3, a / 2);
        else if(c == 0)
            return res + min(a / 3, b / 2);
        return res;
    }
};

复杂度分析：

• 时间复杂度：，无循环，常数时间
• 空间复杂度：，常数空间