Codeforces 643 Div 2. - E. Restorer Distance
時間内にうまく詰めきれなかった……。
まず、$ M = \min(M, A + R)としてよい。なぜなら、$ 1つのブロックを削除して追加することと、$ 1つのブロックを移動することは等価だから。そのうえで、全体を高さ$ kに揃えるのに必要なコストを考える。まずブロックは高さの昇順に左から右に整列しているとして一般性を失わない。すると、高さが$ k以下のブロックのうちもっとも右にあるものの位置を$ pとすれば、追加する必要があるブロック数$ D_A = \sum_{i=1}^p k - h_i、削除する必要があるブロック数は$ D_R = \sum_{i=p+1}^N h_i - kとなる。したがって全体の高さを$ kに揃える最小コストは次式のようになる。
$ m(k) = M\min(D_A, D_R) + \begin{cases} A (D_A - D_R) & \text{if $D_A \gt D_R$} \\ R (D_R - D_A) & \text{otherwise} \end{cases}
さて$ kを$ 0から$ 10^9まで動かして上記の値の最小値を求めれば答えが求まるが、それでは間に合わない。ここで、$ pが変わらない中で$ kを$ 1増やすことを考えると$ D_Aは$ pだけ増え、$ D_Rは$ N - pだけ減る。したがって$ D_Aと$ D_Bの大小関係が変わらなければ、$ m(k)は単調増加ないし単調減少することが分かる。したがって、$ m(k)は各$ h_iおよび$ D_Aと$ D_Bの大小関係が逆転する高さ$ kにおいてだけ計算すればよいことがわかる。ここで$ D_Aと$ D_Bの大小関係が逆転する高さは、$ \dfrac{\sum_i h_i}{N}の前後なので、その値の前後を調べればよい。
code:java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
long A = scanner.nextInt();
long R = scanner.nextInt();
long M = scanner.nextInt();
M = Math.min(M, A + R);
for (int i = 0; i < N; i++) hi = scanner.nextInt(); Arrays.sort(h);
for (int i = 1; i < N; i++) {
}
long min = csumN - 1 * R; for (int i = 0; i < N; i++) min = Math.min(min, cost(N, A, R, M, h, csum, hi)); int k = (int) (csumN - 1 / N); min = Math.min(min, cost(N, A, R, M, h, csum, k));
min = Math.min(min, cost(N, A, R, M, h, csum, k + 1));
System.out.println(min);
}
private static long cost(int N, long A, long R, long M, int[] h, long[] c, int k) {
int i = upperBound(h, k);
long da = (long) k * (i + 1) - ci; long dr = (cN - 1 - ci) - (long) k * (N - i - 1); long cost = Math.min(da, dr) * M;
if (da < dr) {
cost += (dr - da) * R;
} else {
cost += (da - dr) * A;
}
return cost;
}
public static int upperBound(int[] a, int k) {
int left = -1;
int right = a.length;
while (right - left > 1) {
int mid = (left + right) / 2;
left = mid;
} else {
right = mid;
}
}
return left;
}
}