程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 2335 Containers（暴力枚舉）

HDU 2335 Containers（暴力枚舉）

編輯：關於C++

題意：n個40X8的箱子，要求建一個矩形場地來放這些箱子，箱子間有已知大小的間隙，最高可以放5層。求場地的最小面積，在此基礎上盡量方。

思路：設場地x列，y行，那麼x*y == (n+4)/5 所以x不會超過sqrt(n)，所以枚舉x求y就行了。

比賽的時候考慮到隨著x的增加，答案先變小後變大，所以三分的，但是樣例都過不了，後來才注意到是5層。。

細節參見代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 1000000000 + 7;
const int INF = 1000000000;
const int maxn = 100;
int T;
ll n;
struct node {
    ll l, w;
    node(ll l=0, ll w=0):l(l),w(w) {}
};
node cal(ll m1) {
    ll l = 40*m1 + 4*(m1+1);
    ll m2;
    m2 = ceil(n*1.0/m1);
    ll w = 8*m2 + 2*(m2+1);
    return node(l, w);
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%I64d",&n);
        n = (n + 4) / 5;
        ll m = sqrt(n);
        node pre = cal(1LL);
        ll ans_l, ans_w, area = 1LL << 60;
        if(n == 0) {
            printf("0 X 0 = 0\n"); continue;
        }
        for(ll i=1;i<=m;i++) {
            node cur = cal(i);
            if(cur.l * cur.w < area) {
                area = cur.l * cur.w;
                ans_l = cur.l;
                ans_w = cur.w;
            }
            else if(cur.l*cur.w == area && abs(cur.l - cur.w) < abs(ans_l - ans_w)) {
                ans_l = cur.l;
                ans_w = cur.w;
            }
        }
        if(ans_l < ans_w) swap(ans_l, ans_w);
        printf("%I64d X %I64d = %I64d\n",ans_l, ans_w, ans_l*ans_w);
    }
    return 0;
}