Noelちゃんと星々2 [yukicoder No.837] - はまやんはまやんはまやん

前提知識

「マンハッタン距離の差の和の最小値は中央値に集めるとき」

解説

マンハッタン距離の総和の最小値の地点は中央値であるというテクを使う。
高さの変更先は2つあるとのことだが、これは高さYをソートしておくと、
ある地点を境にして合わせる高さが異なる。
なので、その境目を全探索して、2つのグループについてマンハッタン距離の総和の最小値を求める。
　
区間のマンハッタン距離の総和の最小値は、中央値がわかれば、BIT（か累積和）で計算可能である。
get(L,R) := 区間[L,R)を1点に集めるときの距離の総和の最小値

int N; ll Y[101010];
BIT<ll> bit(101010);
//---------------------------------------------------------------------------------------------------
ll get(int L, int R) { // [L, R)
	int C = (L + R) / 2;

	ll res = 0;
	res += 1LL * (C - L) * Y[C] - bit.get(L, C);
	res += bit.get(C, R) - 1LL * (R - C) * Y[C];
	return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> Y[i];
	sort(Y, Y + N);
	rep(i, 0, N) bit.add(i, Y[i]);

	if (Y[0] == Y[N - 1]) {
		cout << 1 << endl;
		return;
	}

	ll ans = infl;
	rep(center, 1, N) chmin(ans, get(0, center) + get(center, N));
	cout << ans << endl;
}