POJ 2014 Flow Layout 模擬解題詳解

這是一道經典的模擬題，要求將一系列小矩形依序放入一個最大寬度固定的大矩形中。當當前行的累積寬度超過最大寬度時，需換行放置。最終需要輸出排版後的整體寬度與高度。

題目大意

給定一個最大寬度 maxwidth，以及一組小矩形的寬高 (width, height)。按照輸入順序依次排放：若將下一個矩形放入當前行會導致行寬超過 maxwidth，則須另起新行。求最終排版後的整體寬度（所有行寬的最大值）與高度（各行最大高度之和）。

解題思路

直接按照題目給定的順序進行模擬即可，無需旋轉或排序。維護四個變數：

• curwidth：當前行已佔用的寬度
• maxheight：當前行中的最大高度
• ans_width：所有行寬的最大值（即最終寬度）
• ans_height：已完成行的高度累計

遍歷每個小矩形：

1. 若 curwidth + width > maxwidth，換行：更新 ans_width = max(ans_width, curwidth)，將 maxheight 累加到 ans_height，並重置 curwidth = width、maxheight = height。
2. 否則留在當前行：curwidth += width，更新 maxheight = max(maxheight, height)，並同步更新 ans_width。

迴圈結束後，最後一行的高度尚未加入 ans_height，需輸出 ans_width x (ans_height + maxheight)。

參考代碼 (C++)

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

const int MAXN = 2000;
struct Rect { int width, height; } a[MAXN];

int main() {
    int maxwidth;
    while (~scanf("%d", &maxwidth), maxwidth) {
        int len = 0;
        while (scanf("%d%d", &a[len].width, &a[len].height)) {
            if (a[len].width == -1 && a[len].height == -1) break;
            len++;
        }
        int ans_height = 0, maxheight = 0, curwidth = 0, ans_width = 0;
        for (int i = 0; i < len; i++) {
            if (curwidth + a[i].width > maxwidth) { // 換行
                ans_width = max(ans_width, curwidth);
                ans_height += maxheight;
                curwidth = a[i].width;
                maxheight = a[i].height;
            } else { // 同行
                curwidth += a[i].width;
                maxheight = max(maxheight, a[i].height);
                ans_width = max(ans_width, curwidth);
            }
        }
        printf("%d x %d\n", ans_width, ans_height + maxheight);
    }
    return 0;
}