磁磚拼貼 題解|APCS 2026 年 6 月初級 第 2 題


簡潔題意

要用磁磚鋪滿 \(H \times W\) 的地面。有 \(N\) 種款式,第 \(i\) 種磁磚高 \(h_i\)、寬 \(w_i\),不能旋轉,要 \(h_i\) 整除 \(H\) 而且 \(w_i\) 整除 \(W\) 才鋪得滿。選這一款時每片成本 \(C_i\) 元、至少要買 \(M_i\) 片,多買的每片可以用 \(S_i\) 元轉賣(\(S_i \le C_i\))。保證至少有一款鋪得滿,輸出最小成本。(\(H, W \le 1000\),\(N \le 100\))

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

  • 子題組 1(\(60\) 分):\(N = 3\)。
  • 子題組 2(\(40\) 分):無額外限制。

一種款式要花多少

  1. 能不能鋪:H % h == 0 && W % w == 0,兩邊都要整除(2.6 的 %、3.3 的 &&)。
  2. 需要幾片:高的方向放 \(H / h\) 片、寬的方向放 \(W / w\) 片,共 need = (H / h) * (W / w) 片。
  3. 實際買幾片:至少 \(M\) 片,所以 buy 是 need 和 \(M\) 之中比較大的那個。
  4. 花多少:買 buy 片花 buy * c,多出來的 buy - need 片轉賣,拿回 (buy - need) * s。需要的比 \(M\) 多時 buy - need 是 \(0\),同一條式子兩種情況都對。

拿範例 1 的第 \(2\) 款驗算:需要 \(2 \times 3 = 6\) 片、至少買 \(8\) 片,花 \(8 \times 8 - 2 \times 2 = 60\) 元。

全部款式:迴圈加擂台

每一款算出花費,用 3.12 的擂台法留下最小的。擂台的初值要比任何一種花費都大,那最貴是多少?地面最大 \(1000 \times 1000\)、磁磚最小 \(1 \times 1\),需要 \(10^6\) 片,每片 \(1000\) 元就是 \(10^9\) 元。初值寫 1000000 這種「看起來夠大」的數是不夠的;直接用 int 能存的最大值 INT_MAX(2.3)最保險。\(10^9\) 還在 int 的範圍內,不需要 long long(2.9)。

子題組 1 的 \(N = 3\),是讓還沒學迴圈的人可以把同一段寫三次;用 4.3 的 for,下面這支程式兩個子題組一起拿。

#include <iostream>
#include <climits>  // INT_MAX 住在這(上冊 2.3)
using namespace std;

int main() {
    int H, W, n;
    cin >> H >> W >> n;
    int best = INT_MAX;  // 比任何一種花費都大
    for (int i = 1; i <= n; i++) {
        int h, w, c, m, s;
        cin >> h >> w >> c >> m >> s;
        if (H % h == 0 && W % w == 0) {
            int need = (H / h) * (W / w);  // 鋪滿需要幾片
            int buy = need;                // 實際買幾片:至少 m 片
            if (buy < m) buy = m;
            int cost = buy * c - (buy - need) * s;  // 多買的轉賣掉
            if (cost < best) best = cost;
        }
    }
    cout << best << endl;
    return 0;
}

測過再交:範例的答案都是「多買再轉賣」

兩個範例的最便宜方案,都是「需要的片數比至少要買的少」。其他情況自己補:

輸入 預期輸出 在測什麼
1 2/1/1 1 5 1 1 10 需要 \(2\) 片、至少買 \(1\) 片:照需要的買,沒有轉賣
2 2/1/1 1 3 4 1 12 需要的片數剛好等於至少要買的片數
1000 1000/1/1 1 1000 1 1 1000000000 最貴的情況:擂台初值夠不夠大
2 3/2/2 2 1 1 1/1 3 7 1 1 14 最便宜的那款高整除、寬不整除,不能用
2 4/2/4 2 1 1 1/1 1 10 1 1 80 第 \(1\) 款轉過來才鋪得滿,但磁磚不能旋轉

這幾筆都親眼看過正確,這題就穩了。

常犯錯誤
  • 不管需要幾片,一律用「買 \(M\) 片、轉賣多的」計算:需要的比 \(M\) 多時 m - need 是負的,等於不夠的那幾片只算了轉賣價。範例全過;1 2/1/1 1 5 1 1 的答案是 \(10\),會印出 \(6\)。本站 \(20\) 筆掛 \(13\) 筆。
  • 「兩邊都要整除」寫成 ||:只要一邊整除就當成鋪得滿。範例全過;2 3/2/2 2 1 1 1/1 3 7 1 1 的答案是 \(14\),會印出 \(1\)。本站 \(20\) 筆掛 \(5\) 筆。
  • 擂台初值設成 1000000:最貴的方案要 \(10^9\) 元。範例全過;1000 1000/1/1 1 1000 1 1 的答案是 \(1000000000\),會印出 \(1000000\)。本站 \(20\) 筆掛 \(3\) 筆。
  • 分成「需要的比較多」「需要的比較少」兩個 if,漏了剛好相等:那一款完全沒算到。範例全過;2 2/1/1 1 3 4 1 的答案是 \(12\),會印出擂台的初值。本站 \(20\) 筆掛 \(3\) 筆。