070 - Plant Planning（★4）

キーワード

• マンハッタン距離

解説

問題 (opens in a new tab)

$x$ と $y$ は独立なので, 個別に考えて良い. $x$ についてのみ考える.

すでに工場がある座標を $x_1, \dots, x_n$ とする.

$x$ に工場を建てると, その時の $x$ についての不便さは $|x_1 - x| + \dots + |x_n - x|$ となる. 次に, $x$ を $x+1$ に動かす.
その時の不便さの変化量は, $(x\text{より左にある工場の個数}) - (x\text{より右にある工場の個数})$ となる.
不便さが最小となるのは, 変化量が $0$ になる時である.
具体的には, $x_1, \dots x_n$ の中央値を取る時に最小値となる.

ただし, ここでは実際の中央値を求める必要はなく, $\lfloor{\frac{n}{2}}\rfloor$ 番目の要素を求めれば十分.
つまり, Aを sort して, A[n/2]とすれば良い.

配列を sort するのに $\mathrm{O}(N\log{N})$ 時間, 不便さを計算するのに $\mathrm{O}(N)$ 時間かかるので, 全体としては $\mathrm{O}(N\log{N})$ 時間で解くことが可能.

提出コード

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
 
func main() {
	n := readInt()
 
	X := make([]int, n)
	Y := make([]int, n)
 
	for i := 0; i < n; i++ {
		scanIntVariables(&X[i], &Y[i])
	}
 
	sort.Slice(X, func(i, j int) bool {
		return X[i] < X[j]
	})
 
	sort.Slice(Y, func(i, j int) bool {
		return Y[i] < Y[j]
	})
 
	sumX := 0
	sumY := 0
 
	lx := X[n/2]
	ly := Y[n/2]
 
	for i := 0; i < n; i++ {
		sumX += abs(X[i] - lx)
		sumY += abs(Y[i] - ly)
	}
 
	writeLine(sumX + sumY)
}