[ZJ] d826. 暗門

http://zerojudge.tw/ShowProblem?problemid=d826

內容 ：

在一個其大無比的空間裡，有 n 個房間相鄰著，譬如第5間的左側是第4間、右側是第6間

現在有 m 個人分別不同的房間。

但因為有些房間太空，有些則是太擠，所以我們要做一些調整，

使得每個房間裡面的人數一樣多。為了達到節能減炭的目的，

我們要讓所有人移動總距離最小。

移動距離的計算方式是：某人從第i移動到第j間，則距離為 |i-j|

輸入說明 ：

每組包含多比測試資料。
第一行給定兩個整數n,m (m為n的倍數)。接著第二行有m個整數，並用空格隔開

分別表示這m個人在哪一個房間裡面。
0 <= n <= m <= 100000。

輸出說明 ：

輸出一個整數，代表總移動距離。

範例輸入 ：

4 81 4 2 3 1 1 2 2

範例輸出 ：

4

提示 ：

出處 ：

(管理：shik)

/**********************************************************************************/
/*  Problem: d826 "暗門" from                                                   */
/*  Language: C                                                                   */
/*  Result: AC (49ms, 659KB) on ZeroJudge                                         */
/*  Author: morris1028 at 2011-06-01 19:58:12                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
int Input() {
    char cha;
    unsigned int x = 0;
    while(cha = getchar())
        if(cha != ' ' && cha != '\n' || cha == EOF) break;
    if(cha == EOF) return -1;
    x = cha-48;
    while(cha = getchar()) {
        if(cha == ' ' || cha == '\n') break;
        x = x*10 + cha-48;
    }
    return x;
}  
main() {
    int n = 5, m =250 , x;
    while(scanf("%d %d", &n, &m) == 2) {
        int a, room[100002] = {0}, U = 1, Ans = 0;
        for(a = 0; a < m; a++) {
            x = Input(), room[x]++;
        }
        m /= n;
        for(a = 1; a <= n; a++) {
            while(room[a] > m) {
                while(room[U] >= m)    U++;
                if(room[a] - m >= m - room[U])
                    Ans += (m-room[U])*abs(U-a), room[a]-= m-room[U], room[U] = m;
                else
                    Ans += (room[a]-m)*abs(U-a), room[U]+= room[a]-m, room[a] = m;
            }
        }
        printf("%d\n", Ans);
    }
    return 0;
}