2016 青島網絡賽 ACM 題「Tea」數學建模與 O(1) 解法詳解

問題重述

茶壺茶量 V ∈ [L, R] (整數區間)。兩茶杯初始為空，需倒茶使：

1. 兩杯茶量差 ≤ 1
2. 茶壺剩余茶量 ≤ 1
3. 最小化倒茶次數

每次倒茶可指定任意實數量，但無法讀取壺中實際剩余量，只知「空/非空」。

樣例邏輯驗證

• L=2, R=2：倒 1 杯 1 单位，另一杯 0。差值 1，壺剩 0~1。答案 1
• L=2, R=4：第一杯倒 1.5。若 V=2，壺剩 0.5，第二杯倒 0.5 (差 1)；若 V=4，壺剩 2.5，第二杯倒 1.5 (差 0)，壺剩 1。答案 2

數學規律推導

情況分類

1. L = R (確定總量)：
   • V ≤ 1：無需倒茶，0 次
   • V = 2：倒 1 次 (1+0)，1 次
   • V ≥ 3：需 2 次 (如 1.5 + 1.5)，2 次
2. L = 0：
   • R = 1：0 次
   • R = 2：1 次
   • R ≥ 3：最優策略每次倒 (R+1)/2，答案 (R+1)/2
3. 一般情況 L > 0 且 L < R：
   • 首輪向兩杯各倒 (L+1)/2 和 (L+1)/2 + 1
   • 若 V ≤ L+2，兩輪結束滿足條件，2 次
   • 否則後續每輪向兩杯各倒 2 单位，直到壺剩 ≤ 1。總次數 = 2 + (R - L - 2 + 1) / 2 = (R - L + 2) / 2

完整 AC 代碼

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    long long L, R;
    while (scanf("%lld%lld", &L, &R) != EOF) {
        if (L == R) {
            if (R <= 1) puts("0");
            else if (R == 2) puts("1");
            else puts("2");
            continue;
        }
        if (L == 0) {
            if (R == 1) puts("0");
            else if (R == 2) puts("1");
            else printf("%lld\n", (R + 1) / 2);
        } else {
            if (L == 1 && R == 2) puts("1");
            else {
                if (L + 2 >= R - 1) puts("2");
                else printf("%lld\n", (R - L + 2) / 2);
            }
        }
    }
    return 0;
}

核心洞察總結

• 問題本質是區間覆蓋與最壞情況優化：倒茶策略必須對區間 [L, R] 所有可能值同時生效
• 首輪倒茶量設計巧妙利用 (L+1)/2 確保下界情況下壺剩 ≤ 1 且杯差 ≤ 1
• 後續固定倒 2 单位維持杯差恆為 1，實現「流水線」式清空
• 最終公式為分段常數時間計算，完美應對 1000 組測試用例、R ≤ 10^16 的大數據範圍