带权中位数

有若干个排列在一条直线上的点pi，每个点上有ai个人，找出一个人使得所有人移动到这个人的位置上的总距离最小。

设 d i s t [ x ] 为 所 有 点 到 P x 的 总 距 离 设dist[x]为所有点到Px的总距离 设dist[x]为所有点到Px的总距离
d i s t [ x ] = ∑ i = 1 x a i ( P x − P i ) + ∑ i = x n a i ( P i − P x ) 1 ◯ d i s t [ x + 1 ] = ∑ i = 1 x + 1 a i ( P x + 1 − P i ) + ∑ i = x + 1 n a i ( P i − P x + 1 ) 2 ◯ dist[x] = displaystylesum_{i=1}^xa_i(P_x - P_i) + displaystylesum_{i=x}^na_i(P_i - P_x) qquad text{textcircled 1}\dist[x+1] = displaystylesum_{i=1}^{x+1}a_i(P_{x+1} - P_i) + displaystylesum_{i=x+1}^na_i(P_i - P_{x+1}) qquad text{textcircled 2} dist[x]=i=1∑x​ai​(Px​−Pi​)+i=x∑n​ai​(Pi​−Px​)1◯dist[x+1]=i=1∑x+1​ai​(Px+1​−Pi​)+i=x+1∑n​ai​(Pi​−Px+1​)2◯
2 ◯ − 1 ◯ = ∑ i = 1 x + 1 a i ( P x + 1 − P i ) + ∑ i = x + 1 n a i ( P i − P x + 1 ) − ∑ i = 1 x a i ( P x − P i ) − ∑ i = x n a i ( P i − P x ) = ∑ i = 1 x a i [ ( P x + 1 − P i ) − ( P x − P i ) ] + ∑ i = x + 1 n a i [ ( P i − P x + 1 ) − ( P i − P x ) ] = ∑ i = 1 x a i ( P x + 1 − P x ) + ∑ i = x + 1 n a i ( P x − P x + 1 ) = ( ∑ i = 1 x a i − ∑ i = x + 1 n a i ) ( P x + 1 − P x ) 状 态 转 移 方 程 ： d i s t [ x + 1 ] = d i s t [ x ] + ( P x + 1 − P x ) ∗ ( x 及 其 之 前 的 人 数 − x + 1 及 其 之 后 的 人 数 ) 若 已 知 d i s t [ 0 ] 可 得 到 所 有 点 到 任 意 目 标 点 的 总 距 离 text{textcircled 2}- text{textcircled 1}\=displaystylesum_{i=1}^{x+1}a_i(P_{x+1} - P_i) + displaystylesum_{i=x+1}^na_i(P_i - P_{x+1}) - displaystylesum_{i=1}^xa_i(P_x - P_i) - displaystylesum_{i=x}^na_i(P_i - P_x) \=displaystylesum_{i=1}^{x}a_i[(P_{x+1} - P_i) -(P_x - P_i)]+displaystylesum_{i=x+1}^na_i[(P_i - P_{x+1}) - (P_i - P_x)]\=displaystylesum_{i=1}^{x}a_i(P_{x+1} -P_x)+displaystylesum_{i=x+1}^na_i(P_x-P_{x+1})\=left( displaystylesum_{i=1}^{x}a_i-displaystylesum_{i=x+1}^na_iright)(P_{x+1} -P_x) \状态转移方程：dist[x+1]=dist[x]+(P_{x+1}-P_x)*(x及其之前的人数-{x+1}及其之后的人数)\若已知dist[0]可得到所有点到任意目标点的总距离 2◯−1◯=i=1∑x+1​ai​(Px+1​−Pi​)+i=x+1∑n​ai​(Pi​−Px+1​)−i=1∑x​ai​(Px​−Pi​)−i=x∑n​ai​(Pi​−Px​)=i=1∑x​ai​[(Px+1​−Pi​)−(Px​−Pi​)]+i=x+1∑n​ai​[(Pi​−Px+1​)−(Pi​−Px​)]=i=1∑x​ai​(Px+1​−Px​)+i=x+1∑n​ai​(Px​−Px+1​)=(i=1∑x​ai​−i=x+1∑n​ai​)(Px+1​−Px​)状态转移方程：dist[x+1]=dist[x]+(Px+1​−Px​)∗(x及其之前的人数−x+1及其之后的人数)若已知dist[0]可得到所有点到任意目标点的总距离

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	static int prefixSums[];
	public static int distSum(int x, int n) {
		int sum = prefixSums[0] * (x - 0);
		for(int i = 1; i < n; ++i) {
			sum += (prefixSums[i] - prefixSums[i - 1]) * Math.abs(x - i);
        }
		return sum;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(bf.readLine());
        String[] strs = bf.readLine().split(" ");
        prefixSums = new int[n];
        prefixSums[0] = Integer.parseInt(strs[0]);
        for(int i = 1; i < n; ++i) {
        	prefixSums[i] = prefixSums[i - 1] + Integer.parseInt(strs[i]);
        }
        int min = Integer.MAX_VALUE;
        int[] dist = new int[n];
        dist[0] = distSum(0, n);
        for(int i = 1; i < n; ++i) {
            dist[i] = dist[i - 1] + prefixSums[i - 1] - (prefixSums[n - 1] - prefixSums[i - 1]);
            if(dist[i] < min)
            	min = dist[i];
        }
        System.out.println(min );
	}
}