10365 Blocks

題目翻譯

給你一個體積 n，要用整數邊長 a, b, c 做出一個長方體，滿足 a * b * c = n。

請求這個長方體最小可能的表面積。

表面積公式是：

2(ab + bc + ca)

輸入

第一行是測資數量 C。
接下來有 C 行，每行包含一個整數 N $(1 \le N \le 1000)$，代表積木數量。

輸出

對於每筆測資，輸出一個整數，代表組成該體積為 N 的長方體所需的最小表面積。

解題思路

可以直接枚舉因數組合：

1. 枚舉 i、j 當作其中兩個邊長。
2. 若 i * j 可以整除 n，就令 h = n / (i * j)，形成一組合法 (i, j, h)。
3. 計算表面積 2 * (i*j + i*h + j*h)，取最小值。

程式裡以雙層迴圈枚舉，遇到不合法組合直接跳過，最後輸出最小答案。

程式碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define idonthavegirlfriend ios::sync_with_stdio(0), cin.tie(0);
#define pb push_back
#define yn(a) (a ? "Yes\n" : "No\n")
// #include <atcoder/fenwicktree>
// #include <atcoder/dsu>
// using namespace atcoder
// author:Jackis666

signed main() {
    idonthavegirlfriend
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        int ans = INT_MAX;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                int area = i * j;
                if (n % area != 0) continue;
                int h = (n + area - 1) / area;
                ans = min(ans, 2 * (h * i + h * j + area));
            }
        }
        cout << ans << "\n";
    }
}