51NOD 1110 距离之和最小 V3(中位数)

X轴上有N个点，每个点除了包括一个位置数据X[i]，还包括一个权值W[i]。点P到点P[i]的带权距离 = 实际距离 * P[i]的权值。求X轴上一点使它到这N个点的带权距离之和最小，输出这个最小的带权距离之和。 Input 第1行：点的数量N。(2 <= N <= 10000) 第2 - N + 1行：每行2个数，中间用空格分隔，分别是点的位置及权值。（-10^5 <= X[i] <= 10^5，1 <= W[i] <= 10^5) Output 输出最小的带权距离之和。 Input示例 5 -1 1 -3 1 0 1 7 1 9 1 Output示例

20

思路:一开始的做法是，从最左端的点开始逐渐往右移动，移动过程中记录左边的贡献和右边的贡献，每次移动更新下当前的带权距离和然后更新下左右贡献即可。

还看到了另一个很好的做法，把每个点的权值w看做是w个点在这，这样就转换成了中位数问题，直接找中位数的那个点就可以了。

方法一代码：

import java.util.Arrays; import java.util.Scanner; class node implements Comparable<node> { int x, w; @Override public int compareTo(node o) { return x - o.x; } } public class Main { static final int maxn = 100005; static node[] a = new node[maxn]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); for (int i = 0; i < maxn; i++) a[i] = new node(); while (sc.hasNext()) { int n = sc.nextInt(); for (int i = 0; i < n; i++) { a[i].x = sc.nextInt(); a[i].w = sc.nextInt(); } Arrays.sort(a, 0, n); int l = a[0].x, r = a[n - 1].x; for (int i = 1; i < n; i++) { if (a[i].x < l) l = a[i].x; if (a[i].x > r) r = a[i].x; } long lval = 0, rval = 0; long dis = 0; for (int i = 0; i < n; i++) { dis += (long) (a[i].x - l) * a[i].w; rval += a[i].w; } long ans = dis; int cur = 0; lval = a[0].w; rval -= a[0].w; for (int i = 1; i < n; i++) { dis -= rval * (a[i].x - a[i - 1].x); dis += lval * (a[i].x - a[i - 1].x); if (dis < ans) ans = dis; rval -= a[i].w; lval += a[i].w; } System.out.println(ans); } } }

方法二代码:

import java.util.Arrays; import java.util.Scanner; class node implements Comparable<node> { int x, w; @Override public int compareTo(node o) { return x - o.x; } } public class Main { static final int maxn = 100005; static node[] a = new node[maxn]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); for (int i = 0; i < maxn; i++) a[i] = new node(); while (sc.hasNext()) { int n = sc.nextInt(); long sum = 0; for (int i = 0; i < n; i++) { a[i].x = sc.nextInt(); a[i].w = sc.nextInt(); sum += a[i].w; } sum /= 2; Arrays.sort(a, 0, n); int num = 0, idx = 0; for (int i = 0; i < n; i++) { num += a[i].w; if (num > sum) { idx = a[i].x; break; } } long ans = 0; for (int i = 0; i < n; i++) { ans += Math.abs((long)(a[i].x-idx)*a[i].w); } System.out.println(ans); } } }