题意整理。

• 规定三个空汽水瓶换一满瓶汽水。并且可以向老板借汽水，兑换之后再还给老板。
• 如果小张手上有n个空汽水瓶，问他能换多少瓶汽水。

方法一（模拟）

1.解题思路

• 定义一个变量count，用于记录每次兑换之后获得的满瓶汽水数。定义一个变量yus，记录兑换之后，还剩余的空汽水瓶数目。
• 模拟整个兑换过程，直到剩余空汽水瓶数n为2或1。如果还剩2个空汽水瓶，则可以向老板借汽水，兑换之后再还给老板，count加1，并终止循环。如果还剩1个空汽水瓶，则无法再换取汽水。

图解展示：

2.代码实现

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            //空汽水瓶个数
            int n=sc.nextInt();
            //可以兑换的满瓶汽水数
            int count=0;
            //每次兑换剩余的空汽水瓶
            int yus=0;
            while(n>=2){
                count+=n/3;
                yus=n%3;
                //每次完成兑换之后还剩余的空汽水瓶数目
                n=n/3+yus;
                //如果只剩2个空汽水瓶，则可以借一瓶，喝完后兑换一瓶满的还给老板
                if(n==2){
                    count++;
                    break;
                }
            }
            if(n!=0){
                System.out.println(count);
            }
        }
    }
}

3.复杂度分析

• 时间复杂度：n每次约变为原来的1/3，所以时间复杂度为$O(lo{g}_{3}n)O(log\_3n)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为$O(1)O(1)$。

方法二（数学）

1.解题思路

由于可以向老板借汽水，兑换之后再还给老板。所以我们能以2个空汽水瓶换到一满瓶汽水。不断以这种方法换汽水，直到没有空瓶子或只有1个空瓶子。只有一个空瓶子时，也不能再换。所以最多能换n/2数目的满瓶汽水。

2.代码实现

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            //空汽水瓶个数
            int n=sc.nextInt();
            if(n!=0){
                System.out.println(n/2);
            }
        }
    }
}

3.复杂度分析

• 时间复杂度：直接输出$n\mathrm{/}2n/2$，所以时间复杂度为$O(1)O(1)$。
• 空间复杂度：不需要额外的空间，所以空间复杂度为$O(1)O(1)$。