[ZJ][dp] a491. 貨物集中問題＠Morris' Blog

2012-11-22 08:38:56| 人氣2,094| 回應0 | 上一篇 | 下一篇

[ZJ][dp] a491. 貨物集中問題

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

一個矩形平面大型倉儲空間，共有 R×C 個分區，其中 R 代表矩形的列數，C 代表矩形的行數。此倉儲空間以一 R×C 二維矩陣表示，倉儲空間中的每一分區以二維座標表示，二維矩陣中每一分區的內容代表各分區的儲存貨物量。今因整個倉儲空間保養維修的因素，需將所有分區的貨物暫時集中於某一分區內，並假設任一分區的容量均可以容納目前倉儲空間中的總貨物容量。因為貨物移動需要移動成本，假定一個單位的貨物從現在的分區移動到相鄰上下左右任意一個分區的成本為 100 元，請寫一程式決定貨物應該集中於那一分區，其整體移動成本為最小。

輸入說明：

第一列有一個整數 N，代表測試資料有幾組。

第二列有兩個數字 R, C, (1 <= R, C <= 2000)分別代表第一組測試資料的二維矩陣列數與行數。接下來的 R 列，每一列有 C 個整數，這 R 列中的第 i 列的第 j 個整數代表 (i, j) 區的儲存貨物量，且均 <=100000。每兩個整數之間都會有一個空白隔開。

輸出說明：

第一列請輸出每一組測試資料貨物應該集中於那一分區 (i, j)，方能使其整體移動成本最小，以兩個整數表示，整數間以一個空白區隔。如有多個分區滿足條件，請輸出字典順序最小者。

第二列請輸出其所需要的最小成本。

範例輸入：

範例輸出：

1 2
2400

提示：

請注意：

1. 原題測資 R, C <=100，與本題要求不盡相同。

2. ZJ 似乎會把換行吃掉，因此輸入格式並非如上所述。

出處：

100 彰雲嘉區學科能力競賽資訊科 (管理：xavier13540)

最近的題目很愛玩優化輸入。
其實這個問題只求移動曼哈頓距離最少的 x, y 座標。
那麼 x y 可以分開討論，找到一個 x 位置最少移動成本。
同理對 y。可以用 O(n) 或者是 O(n^2) 解決都沒差。
反正輸入就是 O(n^2) 了，下面都是用 O(n)。

/**********************************************************************************/
/* Problem: a491 "貨物集中問題" from 100 彰雲嘉區學科能力競賽資訊科*/
/* Language: CPP (1478 Bytes)                                                    */
/* Result: AC(118ms, 295KB) judge by this@ZeroJudge                              */
/* Author: morris1028 at 2012-11-20 16:35:22                                     */
/**********************************************************************************/

#include <stdio.h>
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int t, R, C, i, j, A;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &R, &C);
        long long x[2001] = {}, y[2001] = {}, sum;
        for(i = 1; i <= R; i++) {
            for(j = 1, sum = 0; j <= C; j++) {
                ReadInt(&A);
                y[j] += A, sum += A;
            }
            x[i] = x[i-1] + sum;
        }
        for(i = 1; i <= C; i++)
            y[i] += y[i-1];
        int ax = 1, ay = 1;
        long long ans, tmp = 0;
        long long tot = 0;
        for(i = 1; i <= R; i++)
            tmp += (i-1)*(x[i]-x[i-1]);
        ans = tmp;
        for(i = 2; i <= R; i++) {
            tmp = tmp + x[i-1] - (x[R]-x[i-1]);
            if(tmp < ans)
                ans = tmp, ax = i;
        }
        tot += ans, tmp = 0;
        for(i = 1; i <= C; i++)
            tmp += (i-1)*(y[i]-y[i-1]);
        ans = tmp;
        for(i = 2; i <= C; i++) {
            tmp = tmp + y[i-1] - (y[C]-y[i-1]);
            if(tmp < ans)
                ans = tmp, ay = i;
        }
        tot += ans;
        printf("%d %d\n%lld\n", ax, ay, tot*100);
    }
    return 0;
}

我要檢舉

#a491#貨物集中問題

台長： Morris

您可能對以下文章有興趣

a129. 最小生成樹

[ZJ][單調堆] b123 最大矩形 (Area)

d825. 隔熱紙

[ZJ][多邊形面積] d546. 3. 剪多邊形（molding）

人氣(2,094) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][IDA*] d207. 15 - Puzzle
此分類上一篇:[ZJ][dp] a578. 苦哈哈機器人工廠

回應(0)