题解 | #汽水瓶# 脑筋急转弯

模拟

思路

• 每次拿三个喝完的瓶子去找老板换新汽水，并更新 res、n；
• 等到瓶子不够三个时，则无法再“直接”更换新汽水；
• 但是，如果最后剩下两个瓶子的话，可以和老板先借一个瓶子，喝完再还给老板

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (true) {
            int n = in.nextInt();
            if (n == 0) break;
            int res = 0;
            while (n >= 3) {
                res += n / 3;
                n = n / 3 + n % 3;
            }
            if (n == 2) {
                res++; // 借一个瓶子，喝完再还给老板
            }
            System.out.println(res);
        }
        in.close();
    }
}

• 时间复杂度：$O(logn)O(logn)$
• 空间复杂度：$O(1)O(1)$

脑筋急转弯

看了评论区大佬的解法，才发现自己模拟的解法有多蠢

参考：题解 | #汽水瓶#想要换最多的汽水，就要厚脸皮，每两个空瓶向老板借一瓶

思路

• 题目要求 3 个空瓶子换一瓶水，但是可以借瓶子，所以一旦有两个瓶子就可以去换一瓶新汽水，
• 然后喝完就得到一个空瓶子，最后把空瓶子还给老板就行了。

注意：只有 $11$ 个空瓶子时，啥也干不了

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (true) {
            int n = in.nextInt();
            if (n == 0) break;
            System.out.println(n / 2);
        }
        in.close();
    }
}

• 时间复杂度：$O(1)O(1)$
• 空间复杂度：$O(1)O(1)$