運貨站 題解|APCS 2022 年 10 月中級 第 2 題
簡潔題意
\(R\) 列 \(C\) 行的倉庫(\(1 \le R \le 30\)、\(1 \le C \le 50\)),依序收到 \(n\) 件貨物(\(1 \le n \le 200\))。每件貨物是 A~E 五種固定形狀之一、不能旋轉翻面,最上方那一列固定在第 \(y_i\) 列(保證不會超出倉庫底部)。貨物從倉庫右側進來:先試「剛好完全進入倉庫」的最右位置,放不下(出界或跟已放的貨物重疊)就整件丟棄、倉庫不變;放得下就一格一格往左推,直到再往左會出界或碰到別的貨物為止。輸出最後倉庫的空格數與被丟棄的貨物數。
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(20\) 分):只會出現 B。
- 子題組 2(\(40\) 分):只會出現 A、B、C。
- 子題組 3(\(40\) 分):無額外限制。
先拿下子題組 1(20 分):只有 B,每一列記一個數就夠
B 是「一列三格」。只有 B 的時候每一列各自獨立、互不影響:一件 B 進了第 \(y\) 列就一路往左推到底——不是貼左牆,就是貼在這一列前一件 B 的右邊。所以每一列只要記一個數 w[r]:這一列從左邊數起,前 w[r] 行已經被堵住(一開始全部是 \(0\))。新的 B 要放進第 \(y\) 列時:
w[y] + 3 > C:這一列剩下的空間連三格都不夠,連最右邊都放不下——丟棄。- 否則放得下,而且會一路推到
w[y]旁邊:w[y]加 \(3\),放進去的格數也加 \(3\)。
最後的空格數=\(R \times C\) 減掉放進去的格數。
#include <iostream>
using namespace std;
const int MAX_R = 30;
int main() {
int R, C, n;
cin >> R >> C >> n;
int w[MAX_R] = {}; // w[r]=第 r 列從左數起,前 w[r] 行已經被堵住(一開始全 0)
int placed = 0, discarded = 0;
for (int i = 0; i < n; i++) {
char t;
int y;
cin >> t >> y; // 子題組 1 保證 t 一定是 B:一列三格
if (w[y] + 3 > C) { // 這一列剩下的空間連三格都塞不下
discarded++;
} else {
w[y] += 3;
placed += 3;
}
}
cout << R * C - placed << ' ' << discarded << '\n';
return 0;
}
int w[MAX_R] = {}; 是語法書 6.5 的全部歸零。這份程式交上去,範例 2 和子題組 2、3 大多數的測資會 WA——這是正常的,逐筆給分之下子題組 1 的 \(20\) 分穩穩到手。
從 20 分到 100 分:把倉庫真的畫出來,一格一格往左推
五種形狀一來,「每一列各自獨立」就不成立了:A 一次跨四列、E 跨三列,同一件貨物是一體的——任何一列被擋住,整件就得停。最直接的做法是照題目說的做:開一張 \(R \times C\) 的地圖 occupied 記每一格有沒有貨物,每一件貨物真的從最右邊開始、一格一格往左試。
要試「放在這裡行不行」,得先講清楚形狀的每一格在哪。做法是把形狀打成表——挑「最上列、最右行」那一格當基準點 \((0, 0)\),其他每格記相對於它的位移 (dr, dc),直接照題目附圖抄。A、B、C 左右對稱、不容易抄錯;D 是上面一格靠右、下面一整排三格,E 是上面一格靠右、下面兩列各兩格——這兩個抄的時候對著圖再看一次。基準點放在第 top 列、第 right 行,形狀的每一格就在 (top + dr, right + dc);canPlace 把表跑一遍,任何一格出界或已經有貨物就回傳 false(語法書 7.4 的判斷函式)。
主程式對每一件貨物做四步:
right = C - 1:先試「剛好完全進入倉庫」的最右位置——基準點就在最右一行。- 這裡放不下就
discarded++、直接處理下一件(continue)。不能再往左找:貨物穿不過障礙,障礙左邊的洞是到不了的。 while (canPlace(top, right - 1, cells)) right--;:往左一格還放得下就推——就是一步一步模擬移動,只是方向固定往左、停下來的條件是「下一格放不下」。- 停下來之後把這幾格標成已佔用、累加放進去的格數。
#include <bits/stdc++.h>
using namespace std;
const int MAX_R = 30;
const int MAX_C = 50;
// 五種形狀打成表:每個方格相對於「最上列、最右行」的位移 (dr, dc)
// 格數不一樣:表開到最多的 5 格,cnt[t] 記第 t 種實際有幾格
int cnt[5] = {4, 3, 4, 4, 5};
pair<int, int> shape[5][5] = {
{{0, 0}, {1, 0}, {2, 0}, {3, 0}}, // A
{{0, -2}, {0, -1}, {0, 0}}, // B
{{0, -1}, {0, 0}, {1, -1}, {1, 0}}, // C
{{0, 0}, {1, -2}, {1, -1}, {1, 0}}, // D
{{0, 0}, {1, -1}, {1, 0}, {2, -1}, {2, 0}} // E
};
int R, C;
bool occupied[MAX_R][MAX_C]; // 全域陣列:一開始全是 false
// 把第 t 種形狀的最右行放在第 right 行、最上列放在第 top 列,放得下嗎?
bool canPlace(int top, int right, int t) {
for (int i = 0; i < cnt[t]; i++) {
auto [dr, dc] = shape[t][i];
int r = top + dr, c = right + dc;
if (r < 0 || r >= R || c < 0 || c >= C) return false; // 出界
if (occupied[r][c]) return false; // 撞到別的貨物
}
return true;
}
int main() {
int n;
cin >> R >> C >> n;
int used = 0, discarded = 0;
while (n--) {
char type;
int top;
cin >> type >> top;
int t = type - 'A'; // A~E 變成 0~4
int right = C - 1; // 先試「剛好完全進入倉庫」的最右位置
if (!canPlace(top, right, t)) { discarded++; continue; }
while (canPlace(top, right - 1, t)) right--; // 還能往左就繼續推
for (int i = 0; i < cnt[t]; i++) {
auto [dr, dc] = shape[t][i];
occupied[top + dr][right + dc] = true;
}
used += cnt[t];
}
cout << R * C - used << ' ' << discarded << '\n';
return 0;
}
shape[t][i] 是第 t 種形狀的第 i 格:五種形狀格數不一樣,表開到最多的 \(5\) 格、另用 cnt[t] 記實際有幾格(二維陣列,語法書 6.9)。auto [dr, dc] 是結構化綁定,把一個 pair 一次拆成兩個變數。速度不用擔心:最多 \(200\) 件貨物、每件最多往左推 \(50\) 格、每格查 \(5\) 個方格,總共 \(200 \times 50 \times 5 = 50000\) 次上下。
更簡潔的寫法:每一列還是只記一個數
回頭看子題組 1:那時每一列只記「被堵到第幾行」就夠了。這個想法其實五種形狀都適用,靠的是兩個觀察:
- 五種形狀的每一列都是連續的、而且靠右對齊——每一列最右邊那格全在同一行(D 是
..#/###,E 是.#/##/##)。所以一個形狀只要記「由上到下每一列有幾格」:A{1,1,1,1}、B{3}、C{2,2}、D{1,3}、E{1,2,2}。 - 貨物只會水平移動、而且只從右邊進來——第 \(r\) 列一旦有格子被佔到第 \(c\) 行,第 \(c\) 行左邊的空格(不管是不是洞)之後任何貨物都到不了。所以每一列只要一個數
w[r]=這一列從左數起前w[r]行已經到不了;那一列裡真正有幾格是貨物、有幾格是洞,都不用管。
於是一件貨物放進第 \(y\) 列的過程變成:形狀的第 \(i\) 列(倉庫的第 \(y + i\) 列)有 tile[i] 格,它的右邊界至少要到 w[y + i] + tile[i] 才不會撞到東西;整件貨物是一體的,所以最後停下來的右邊界是各列的最大值 ma。任何一列 w[y + i] + tile[i] > C(連最右邊都塞不下)就丟棄;否則這幾列的 w 全部改成 ma——包括格數少的那幾列(D 上面那列只有一格,這一列的牆同樣要推到 ma:它左邊的格子從此到不了)。
空格數仍然是 \(R \times C\) 減掉放進去的格數(每種形狀幾格=grid_num),不能拿 w 加總——被堵在後面的洞到不了、卻仍然是空格。
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_R = 30;
// 五種形狀「由上到下每一列有幾格」:每一列都靠右對齊,所以只記寬度就夠
// 高度不一樣:表開到最高的 4 列,height[t] 記第 t 種實際有幾列
int tiles[5][4] = {
{1, 1, 1, 1}, // A
{3}, // B
{2, 2}, // C
{1, 3}, // D
{1, 2, 2} // E
};
int height[5] = {4, 1, 2, 2, 3}; // 每種形狀共幾列
int grid_num[5] = {4, 3, 4, 4, 5}; // 每種形狀共幾格
int R, C;
// 把形狀 tile(共 h 列)的最上列放在第 y 列往左推:放得下就更新 w 並回傳 true,放不下回傳 false
bool push(int tile[], int h, int y, int w[]) {
int ma = 0; // 推完之後整件貨物共同的右邊界(佔到第 ma - 1 行)
for (int i = 0; i < h; i++) {
if (tile[i] + w[y + i] > C) return false; // 這一列連最右邊都塞不下
ma = max(ma, tile[i] + w[y + i]);
}
for (int i = 0; i < h; i++) {
w[y + i] = ma; // 整件貨物一起停:這幾列的牆都推到 ma
}
return true;
}
int main() {
int n;
cin >> R >> C >> n;
int w[MAX_R] = {}; // w[r]=第 r 列從左數起前 w[r] 行已經到不了(一開始全 0)
int ans = R * C;
int drop_cnt = 0;
for (int i = 0; i < n; i++) {
char t;
int y;
cin >> t >> y;
if (push(tiles[t - 'A'], height[t - 'A'], y, w)) {
ans -= grid_num[t - 'A'];
} else {
drop_cnt++;
}
}
cout << ans << ' ' << drop_cnt << '\n';
}
陣列傳進函式,函式裡改的就是 main 裡那一份 w(語法書 7.7);tiles[t - 'A'] 用字元相減把 A~E 變成 \(0 \sim 4\),傳進去的是 tiles 的那一列。五種形狀高度不一樣,tiles 開到最高的 \(4\) 列、另用 height[] 記每種形狀實際有幾列,沒用到的格子不會被讀到。
兩種寫法答案完全一樣、都是滿分。模擬版照題意做、不需要任何觀察;簡潔版少開一張地圖、程式短了一半,但它成立的前提是「每一列靠右對齊、只水平移動」——形狀或規則一變(例如某個形狀有一列不靠右),還是得回到模擬版。
測過再交:範例沒有 D,也抓不到 E 抄反
範例 1 只有 B——它只是子題組 1 的驗收。範例 2 有 C、A、E、B,卻沒有 D;更麻煩的是它連 E 抄反都抓不到:把 E 左右鏡射成 #./##/## 跑範例 2,E 上面那一格會落在不同的行,最後的空格數和丟棄數卻一模一樣。「形狀有沒有抄對」是這題最容易錯、範例又幾乎不幫你檢查的地方,用手算得動的小倉庫自己補:
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
2 3 1 / D 0 |
2 0 |
D 剛好貼右牆放進 \(2 \times 3\),上面那列左邊兩格是永遠到不了的洞——但洞仍然是空格。把 w 加總當佔用格數的程式印 0 0 |
2 4 2 / B 0 / D 0 |
1 0 |
範例沒有 D:D 上面那一格卡在 B 右邊、下面三格在 B 底下,剛好放得下、一格都推不動。D 左右抄反或上下抄反的程式都會把 D 丟掉,印 5 1 |
3 4 2 / B 0 / E 0 |
4 0 |
同一件事換成 E:E 抄反、或是把貨物從左邊往右推的程式印 9 1——這幾種錯兩個範例都抓不到 |
1 3 2 / B 0 / B 0 |
0 1 |
剛好貼牆算放得下、第二件才丟棄:寫成 >= C 就丟棄的程式印 3 2。子題組 1 版就能驗 |
四筆都親眼看過正確,這題就穩了。
常犯錯誤
- 最右邊放不下就往左繼續找位置:貨物穿不過障礙、到不了障礙左邊的洞。範例 2 的
B 0會被塞進第 0 列左邊,印10 1(該印13 2)。 - D、E 抄反(左右鏡射或上下顛倒),或把貨物從左邊往右推:A、B、C 左右對稱、看不出差別,兩個範例全過(範例 2 有 E 也一樣);自測表第 2、3 列印
5 1/9 1。 - 每一列各自往左推(
w[y + i] += tile[i],忘了整件貨物要一起停):範例 2 印10 1。 - 用
w加總當佔用格數:被堵住的洞也是空格。範例 1 過、範例 2 印3 2。 w[y + i] + tile[i] >= C就丟棄:剛好貼右牆是放得下的。範例 1 過、範例 2 印17 3。- 判定放不下之後忘了
continue:丟棄的貨物照樣被往左推、被標記。範例 1 印2 2。