HDU 2335 Containers：暴力枚舉尋找最小面積場地

問題描述

n 個 40×8 的箱子，需建矩形場地存放。箱子間有固定間隙，最多堆 5 層。求場地最小面積，面積相同時盡量接近正方形（長寬差最小）。

關鍵觀察

• 每層放 x 列、y 行箱子，共 x·y 個/層。
• 5 層共可放 5·x·y 個，需 5·x·y ≥ n → x·y ≥ ceil(n/5)。
• 場地長寬：

  L = 40*x + 4*(x+1) = 44x + 4
      W = 8*y + 2*(y+1) = 10y + 2

• x 最大約 sqrt(n/5)，直接枚舉 x 計算 y = ceil(m/x)（m = ceil(n/5)）。

演算法

1. m = (n + 4) / 5（向上取整）。
2. 枚舉 x = 1 ~ sqrt(m)，計算 y = ceil(m/x)。
3. 計算面積 L·W，記錄最小面積；面積相同取 |L-W| 最小者。
4. 輸出 max(L,W) X min(L,W) = area。

完整程式碼

#include 
using namespace std;
typedef long long ll;

struct Dim { ll l, w; };

Dim calc(ll x, ll n) {
    ll y = (n + x - 1) / x;  // ceil
    return {44*x + 4, 10*y + 2};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        ll n; cin >> n;
        n = (n + 4) / 5;  // 總格數
        if (n == 0) { cout << "0 X 0 = 0\n"; continue; }
        
        ll bestArea = LLONG_MAX, bestL=0, bestW=0;
        for (ll x = 1; x*x <= n; ++x) {
            Dim d = calc(x, n);
            ll area = d.l * d.w;
            if (area < bestArea || (area == bestArea && abs(d.l - d.w) < abs(bestL - bestW))) {
                bestArea = area; bestL = d.l; bestW = d.w;
            }
        }
        if (bestL < bestW) swap(bestL, bestW);
        cout << bestL << " X " << bestW << " = " << bestArea << "\n";
    }
    return 0;
}

複雜度

• 時間：O(T·√n)，n≤1e9 時 √n≈3e4 極快。
• 空間：O(1)。