题目分析

核心问题：高川有 n 个空饮料瓶。商店的规则是 3 个空瓶可以换 1 瓶新饮料。喝完新饮料又会得到一个空瓶。问题是，在允许向老板借瓶子（并最终归还）的情况下，高川最多能喝到多少瓶饮料？ 关键规则：题目描述中的 “借瓶子” 策略是解题的关键。这意味着我们总能将兑换进行到只剩下 1 个或 2 个空瓶为止，因为： 如果最后剩 2 个空瓶，可以借 1 个，凑成 3 个换 1 瓶，喝完后把空瓶还给老板。 如果最后剩 1 个空瓶，则无法再兑换。

思路分析

这道题有两种主要的解法：一种是模拟兑换过程的循环法，另一种是通过数学推导得出的公式法。题目备注中提示我们尽量使用 O (1) 的方法，这暗示了公式法是更优的选择。

方法一：模拟循环法 (O (log n))

这种方法直观地模拟了兑换过程。 初始化：设 total_drunk = 0 记录总共喝的饮料数，current_bottles = n 记录当前拥有的空瓶数。 循环兑换：只要 current_bottles 大于等于 3，就一直进行兑换。 计算兑换： 计算能兑换多少瓶新饮料：exchanged = current_bottles / 3。 将新喝的饮料数加到总数上：total_drunk += exchanged。 更新当前的空瓶数：喝完 exchanged 瓶饮料后，会得到 exchanged 个新空瓶。加上兑换后剩下的空瓶 current_bottles % 3，总数为 current_bottles = exchanged + (current_bottles % 3)。 结束：当 current_bottles < 3 时，循环结束。此时 total_drunk 就是答案。 为什么是 O (log n)？ 每次循环，空瓶数 current_bottles 至少会减少到原来的一半左右（例如，9 个换 3 个，变成 4 个；6 个换 2 个，变成 3 个）。因此，循环次数与 n 的对数成正比。

方法二：数学公式法 (O (1))

我们可以从另一个角度思考这个问题。 兑换本质：每兑换一次，我们消耗 3 个空瓶，但又得到 1 个新空瓶。所以，每喝到 1 瓶新饮料，实际上消耗了 2 个空瓶。 建立关系：设总共喝了 x 瓶饮料。那么，为了喝到这 x 瓶饮料，我们总共消耗了 2 * x 个空瓶。 最终状态：喝完所有能喝的饮料后，我们手里会剩下 r 个空瓶，其中 r 只能是 1 或 0（因为剩 2 个可以借 1 个再换 1 瓶，喝完后 r 变为 0）。 列方程：我们最开始有 n 个空瓶。这 n 个空瓶一部分被消耗掉了，一部分剩下了。所以有： n = (消耗的空瓶数) + (剩下的空瓶数) n = 2 * x + r 求解：我们要求解 x，即 x = (n - r) / 2。 最大化 x：为了让喝到的饮料 x 最多，我们需要让剩下的空瓶 r 尽可能小。 如果 n 是奇数，n-1 是偶数，r=1 时 x=(n-1)/2。 如果 n 是偶数，n-0 是偶数，r=0 时 x=n/2。 这个分段函数可以用一个统一的数学表达式来表示：x = (n - 1) // 2。这里的 // 表示整数除法（向下取整）。 我们来验证一下： 当 n = 10 (偶数) 时，(10 - 1) // 2 = 9 // 2 = 4。这与样例 5 不符。 当 n = 1 (奇数) 时，(1 - 1) // 2 = 0 // 2 = 0。这与样例 0 相符。 问题出在哪里？上面的推导有一个小缺陷。对于 n=10，10/2=5 是正确答案。对于 n=9，(9-1)/2=4，但实际上可以换 3 瓶，喝完得 3 个空瓶，再换 1 瓶，总共喝 4 瓶，(9-1)/2=4 是正确的。对于 n=8，(8-0)/2=4，可以换 2 瓶剩 2 空瓶，喝完有 4 空瓶，再换 1 瓶剩 1 空瓶，喝完有 2 空瓶，借 1 换 1 瓶，总共喝 4 瓶，(8-0)/2=4 是正确的。 修正推导：让我们重新审视 n = 2 * x + r 这个方程。 如果 n 是奇数，n=2k+1，那么 r 必须是 1，x=k。即 x = (n-1)/2。 如果 n 是偶数，n=2k，那么 r 必须是 0，x=k。即 x = n/2。 这两个情况可以合并成一个更简洁的数学表达式：x = n // 2。这里的 // 是整数除法（向下取整）。 我们再验证一下： n = 10 (偶数), 10 // 2 = 5。正确。 n = 1 (奇数), 1 // 2 = 0。正确。 n = 2 (偶数), 2 // 2 = 1。（借 1 瓶，换 1 瓶，喝完还 1 瓶）正确。 n = 3 (奇数), 3 // 2 = 1。（换 1 瓶，喝完剩 1 瓶）正确。 n = 4 (偶数), 4 // 2 = 2。（3 换 1，剩 2，借 1 换 1，喝完还 1）正确。 这个公式 x = n // 2 完美地解决了问题。 算法设计 根据上面的分析，我们采用公式法。 读取输入：首先读取测试用例的数量 T。 处理每个测试用例： 读取一个整数 n。 直接计算 n // 2。 输出计算结果。 这个算法的时间复杂度是 O(1)，空间复杂度也是 O(1)，完全满足题目要求，并且能高效处理 n 高达 10^18 的情况。 C++ 代码实现:

#include <iostream>

// 使用 long long 以处理 n 达到 10^18 的情况
using ll = long long;

int main() {
    // 提高C++ I/O效率
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;

    while (t--) {
        ll n;
        std::cin >> n;

        // 直接应用公式：n // 2
        // 在C++中，整数除法对于正数就是向下取整
        std::cout << n / 2 << "\n";
    }

    return 0;
}

代码解释

using ll = long long;：定义一个类型别名 ll 来代表 long long 类型。这是因为题目中 n 的最大值是 10^18，超出了 32 位整数 int 的范围，必须使用 64 位整数 long long。 std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);：这是竞赛编程中常用的输入输出优化，可以加速 cin 和 cout。 while (t--)：循环处理 t 个测试用例。 ll n; std::cin >> n;：读取当前测试用例的空瓶数 n。 std::cout << n / 2 << "\n";：这是代码的核心。它直接计算 n 除以 2 的整数结果并输出。在 C++ 中，当两个整数相除时，如果结果为正，会自动进行向下取整，这正是我们公式 n // 2 所需要的。