磁磚拼貼 題解|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\) 分):無額外限制。
一種款式要花多少
- 能不能鋪:
H % h == 0 && W % w == 0,兩邊都要整除(2.6 的%、3.3 的&&)。 - 需要幾片:高的方向放 \(H / h\) 片、寬的方向放 \(W / w\) 片,共
need = (H / h) * (W / w)片。 - 實際買幾片:至少 \(M\) 片,所以
buy是need和 \(M\) 之中比較大的那個。 - 花多少:買
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\) 筆。