2011-06-01 22:15:22Morris
d826. 暗門
http://zerojudge.tw/ShowProblem?problemid=d826
內容 ：
在一個其大無比的空間裡，有 n 個房間相鄰著，譬如第5間的左側是第4間、右側是第6間
現在有 m 個人分別不同的房間。
但因為有些房間太空，有些則是太擠，所以我們要做一些調整，
使得每個房間裡面的人數一樣多。為了達到節能減炭的目的，
我們要讓所有人移動總距離最小。
移動距離的計算方式是：某人從第i移動到第j間，則距離為 |i-j|
現在有 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
提示 ：
出處 ：
/* 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;
}
下一篇：d825. 隔熱紙