程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2335 Containers(暴力枚舉)

HDU 2335 Containers(暴力枚舉)

編輯:C++入門知識

HDU 2335 Containers(暴力枚舉)


題意: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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved