1518. 换酒问题

小区便利店正在促销，用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 numBottles 瓶酒。

如果喝掉了酒瓶中的酒，那么酒瓶就会变成空的。

请你计算 最多 能喝到多少瓶酒。

/**
	学会从总体上考虑问题，训练思维
*/

//方法一：正常模拟

//开始有n瓶酒，所以ans = n；当且仅当n >= m 时，可以继续喝到酒（兑换）,
//兑换后可以得到 a = （下取整）n / m ; 
//剩下 n % m 个，所以还剩下 a + n % m 个瓶子，
//继续兑换
class Solution {
    public int numWaterBottles(int n, int m) {
    	int ans = n;
        while (n >= m) {
        	int a = n / m;
            int b = n % m;
            ans += a;
            n = a + b;
        }
        return ans;
    }
}


//方法二：整体考虑，每次兑换会减少 m - 1个瓶子，拿m个瓶子兑换 1 瓶酒。
//利用每个交易会损失瓶子个数m - 1为定值，可以算出最大交换次数（额外的
//饮用次数）cnt = (向下取整) (n / (m - 1)),加上起始瓶子就是答案。
class Solution {
    public int numWaterBottles(int n, int m) {
    	int cnt = n / (m - 1);
        return n % (m - 1) == 0 ? cnt + n - 1 : cnt + n;
    }
}

• 注意边界条件：当n为m-1的倍数时，最后一个回合不满足兑换条件，因为最后一个交易回合剩下m-1个酒瓶，不够要求的兑换数量m。

面试题(换酒问题的变体)

• 初始有n/2瓶汽水，numExchange 分别为2和4(m = 2 or m = 4),问最多能喝多少瓶汽水。

class Solution {
	//方法一
    public int numWaterBottles(int numBottles, int numExchange) {
    	//capExtra 是 初始 n/2 个酒瓶，4换一，能喝到的总数
    	int capExtra = numBottles(n/2, 4);
        //bottleExtra 是 初始 n/2 个酒瓶，2换一，能喝到的总数
        int bottleExtra = numBottles(n/2, 2);
        //多算了一边初始值，所以要减掉
        return capExtra + bottleExtra - n / 2;
    }
    public int numBottles(int n, int m) {
    	int ans = n;
        while (n >= m) {
        	int a = n / m;
            int b = n % m;
            ans += a;
            n = a + b;
        }
        return ans;
    }
}

class Solution {
	//方法二
    public int numWaterBottles(int numBottles, int numExchange) {
    	numBottles = n / 2;//瓶子和瓶盖初始数量；
        numExchange = 2;//瓶子的兑换
        int bottleExtra = numBottles % numExchange == 0 ? 
        				numExchange / (numExchange - 1) - 1 : 
                        numExchange / (numExchange - 1);
        numExchange = 4;//盖子的兑换
        int capExtra = 	numBottles % numExchange == 0 ? 
        				numExchange / (numExchange - 1) - 1 : 
                        numExchange / (numExchange - 1);
        return numBottles + bottleExtra + capExtra;
    }
}