解题思路

  1. 问题分析：

    • 每3个空瓶可以换1瓶汽水
    • 喝完后又会产生新的空瓶
    • 2个空瓶时可以借1个空瓶换1瓶汽水
    • 1个空瓶时无法继续换取

  2. 处理流程：

    初始状态：10个空瓶
第1轮：10/3=3瓶汽水，剩余1个空瓶，新增3个空瓶，共4个空瓶
第2轮：4/3=1瓶汽水，剩余1个空瓶，新增1个空瓶，共2个空瓶
第3轮：2个空瓶，借1个换1瓶汽水
总计：3+1+1=5瓶汽水

  3. 关键点：

    • 每轮循环处理3个空瓶换1瓶的情况
    • 每轮更新剩余空瓶数 = 换不了的空瓶 + 新喝完的空瓶
    • 最后特殊处理2个空瓶的情况

代码

#include <iostream>
using namespace std;

int getDrinks(int bottles) {
    if (bottles < 2) {
        return 0;
    }
    
    // 每3个空瓶换1瓶汽水
    int total = 0;
    while (bottles >= 3) {
        // 当前可以换到的汽水数
        int newDrinks = bottles / 3;
        total += newDrinks;
        // 剩余的空瓶 = 换不了的空瓶 + 新喝完的空瓶
        bottles = bottles % 3 + newDrinks;
    }
    
    // 如果最后剩2个空瓶，还可以找老板借1个空瓶换1瓶汽水
    if (bottles == 2) {
        total += 1;
    }
    
    return total;
}

int main() {
    int n;
    while (cin >> n && n) {
        cout << getDrinks(n) << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static int getDrinks(int bottles) {
        if (bottles < 2) {
            return 0;
        }
        
        // 每3个空瓶换1瓶汽水
        int total = 0;
        while (bottles >= 3) {
            // 当前可以换到的汽水数
            int newDrinks = bottles / 3;
            total += newDrinks;
            // 剩余的空瓶 = 换不了的空瓶 + 新喝完的空瓶
            bottles = bottles % 3 + newDrinks;
        }
        
        // 如果最后剩2个空瓶，还可以找老板借1个空瓶换1瓶汽水
        if (bottles == 2) {
            total += 1;
        }
        
        return total;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            System.out.println(getDrinks(n));
        }
        sc.close();
    }
}

def get_drinks(bottles):
    if bottles < 2:
        return 0
    
    # 每3个空瓶换1瓶汽水
    total = 0
    while bottles >= 3:
        # 当前可以换到的汽水数
        new_drinks = bottles // 3
        total += new_drinks
        # 剩余的空瓶 = 换不了的空瓶 + 新喝完的空瓶
        bottles = bottles % 3 + new_drinks
    
    # 如果最后剩2个空瓶，还可以找老板借1个空瓶换1瓶汽水
    if bottles == 2:
        total += 1
        
    return total

def main():
    while True:
        try:
            n = int(input())
            if n == 0:
                break
            print(get_drinks(n))
        except EOFError:
            break

if __name__ == "__main__":
    main()

算法及复杂度

  1. 算法：贪心算法

    • 每次尽可能多地用3个空瓶换汽水
    • 最后处理特殊情况（2个空瓶）

  2. 时间复杂度：

    • 每次循环瓶子数量至少减少为原来的1/3
    • 假设初始n个瓶子，经过k轮后：
    • 解得：
    • 因此时间复杂度为

  3. 空间复杂度：

    • 只需要常数级别的变量存储
    • 不需要额外的数据结构