Editorial for 裝飲料 (APCS 2024-10 初級)

簡潔題意

杯子內層是上下兩個長方體：下層底面 \(w_1 \times w_1\)、高 \(h_1\)，上層底面 \(w_2 \times w_2\)、高 \(h_2\)。依序倒入 \(n\) 杯水（體積 \(V_1, \ldots, V_n\)），杯滿後水位就停在杯口。求單次倒水的水位上升量的最大值（\(1 \le n \le 10\)、\(1 \le w_1, w_2, h_1, h_2 \le 50\)、每杯不超過 \(10^4\)；題目保證每次上升的高度都是整數）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(60\) 分）：\(n = 1\)。只倒一次，注水後的高度就是答案。
  • 子題組 2（\(40\) 分）：無額外限制。

核心觀察：別追水，直接用總水量算水位

「這杯水有多少留在下層、多少進了上層」很難追。換個方向想：水位只由杯裡的總水量決定。設下層裝滿要 \(V_{\text{下}} = w_1^2 h_1\)、整杯容量 \(V_{\text{滿}} = w_1^2 h_1 + w_2^2 h_2\)，那麼總水量 \(V\) 對應的水位只有三種情況：

  • \(V \ge V_{\text{滿}}\)：滿了，水位停在杯口 \(h_1 + h_2\)。
  • \(V \le V_{\text{下}}\)：水都在下層，水位 \(= V / w_1^2\)。
  • 介於中間：下層淹滿了，水位 \(= h_1 + (V - V_{\text{下}}) / w_2^2\)。

「這次倒水上升多少」＝新水位 \(-\) 舊水位。題目保證上升量都是整數，所以上面的除法都是整除，用 int 的除法不會偷掉小數；數字最大也就 \(50 \times 50 \times 50 \times 2 = 250000\)，int 綽綽有餘。

先拿下子題組 1（\(60\) 分）：一杯水，三個 if

\(n = 1\) 時就是「算一次水位」：讀進規格和那一杯的體積，套上面的三種情況，印出來——連迴圈都不用，只用到語法書上冊第三單元為止的語法。

注意：「滿了」那個分支不能省——只倒一杯也可能直接溢出來（杯子可以很小）。

#include <iostream>
using namespace std;

int main() {
    int n, w1, w2, h1, h2, v;
    cin >> n;                   // 子題組 1 保證 n = 1
    cin >> w1 >> w2 >> h1 >> h2;
    cin >> v;

    int lowerVol = w1 * w1 * h1;            // 下層裝滿的水量
    int fullVol = lowerVol + w2 * w2 * h2;  // 整個杯子的容量

    int height;                 // 倒完後的水位：分三種情況
    if (v >= fullVol) {
        height = h1 + h2;                       // 裝滿了，停在杯口
    } else if (v <= lowerVol) {
        height = v / (w1 * w1);                 // 還在下層
    } else {
        height = h1 + (v - lowerVol) / (w2 * w2); // 淹過下層，算上層
    }
    cout << height << endl;     // 只倒一次：上升量就是水位本身
    return 0;
}

這一版穩穩拿下子題組 1 的 \(60\) 分（範例 1 會過；範例 2、3 有很多杯水，它只讀第一杯，答案對不對就要看運氣了）。

從 \(60\) 分到 \(100\) 分：每倒一杯，重算一次水位

多杯水也是同一件事重複做：累積總水量 total，每倒一杯就用三種情況重算一次水位，上升量 \(=\) 新水位 \(-\) 上次的水位 prev，用擂台記住最大值。水位不會下降，上升量至少是 \(0\)，所以擂台從 \(0\) 開始就安全。新增的語法只有第四單元的單層 for——不需要陣列。

#include <iostream>
using namespace std;

int main() {
    int n, w1, w2, h1, h2;
    cin >> n;
    cin >> w1 >> w2 >> h1 >> h2;

    int lowerVol = w1 * w1 * h1;            // 下層裝滿的水量
    int fullVol = lowerVol + w2 * w2 * h2;  // 整個杯子的容量

    int total = 0;      // 目前杯裡的水量
    int prev = 0;       // 上一次倒完的水位
    int best = 0;       // 上升量的最大值
    for (int i = 1; i <= n; i++) {
        int v;
        cin >> v;
        total += v;

        int height;     // 現在的水位：分三種情況
        if (total >= fullVol) {
            height = h1 + h2;                             // 滿了，停在杯口
        } else if (total <= lowerVol) {
            height = total / (w1 * w1);                   // 還在下層
        } else {
            height = h1 + (total - lowerVol) / (w2 * w2); // 淹過下層，算上層
        }

        if (height - prev > best) {     // 擂台：這一次的上升量
            best = height - prev;
        }
        prev = height;
    }
    cout << best << endl;
    return 0;
}

測過再交：範例的「溢出」溢得太客氣

範例 3 有溢出，但只超過一點點——「忘了封頂」的程式在那種情況常常還是對的（整數除法幫它蓋掉了）。自己補幾筆狠一點的：

輸入 正確輸出 在測什麼
1 ／ 2 3 4 5 ／ 10000 9 一杯就狂溢：沒封頂的程式會印出幾百的水位
2 ／ 2 3 4 5 ／ 61 50 9 第一杯剛好裝滿：第二杯上升量是 \(0\)，不能變成負的或亂數
1 ／ 5 10 12 8 ／ 300 12 水面剛好停在下層頂：\(V \le V_{\text{下}}\) 的等號情況

三個都親眼看過正確，這題就穩了。

常犯錯誤
  1. 忘了「滿了就停」：水位算到杯口之上。範例 1、2 都矇得過、範例 3 也只差一點（印 30）——自測表第一列會讓它現形得很徹底。
  2. 求成「最後的水位」不是「上升量的最大值」：\(n = 1\) 時兩者剛好一樣，子題組 1 全對，卡在 \(60\) 分上不去。範例 2 當場現形（印 19，正確是 13）。
  3. 忘了乘成底面「積」：底面積是 \(w^2\) 不是 \(w\)。範例 1 當場現形（印 13）。
  4. 整杯都用下層的底面積除：水淹過下層後，上面那段要用 \(w_2^2\) 算。範例 1 當場現形（印 12，正確是 10）。