《程序员》2007第八期之算法擂台 博客分类： 算法相关 算法J#

题目描述（手头没书，不知道有没有记错）：有v个在一条直线上的村庄，要在其中的p个村庄上修建邮局。每个村庄将会选择离其最近的村庄收发邮件。现在要选择这p个邮局的修建地址，使得这v个村庄到邮局的总路程尽可能少。
输入：首先是两个正整数v,p，表示村庄个数与邮局个数。
      然后是v个不小于零的整数，表示v个村庄的坐标。
输出：p从小到大个用空格分开的整数，表示p个邮局的坐标。


这个题目用简单的重举法显然是行不通的，那样时间复杂度将达到阶乘级别。
我用的是动态规划，时间复杂度为O(n*n*(n+p)).不知道有没有更好的算法。

注意：这个题目的解实际上不唯一，比如v=2,p=1的情形，邮局修在村庄1与村庄2是一样的。[/color]

/**
 * &#Postoffice.java
 * 算法描述:
 *     记m(i,j)为前i个村庄设置j个邮局时最小的总路程,
 *     s(i,j)为从村庄i到j中(包括i,j)中设置一个村庄时需要的最小路程,则有:
 *     m(i,j) ＝min{ m(k,j-1)+s(k,i-1) : j-1<＝k<＝i-1}
 * 则状态总数为 O(n*(p+n)),转移代价为O(n),故总体时间复杂度为O(n*n*(n+p))
 * @author Eastsun
 * @version 2.0 2008/8/27
 */
package eastsun.algorithm;

import java.util.*;

public class Postoffice {

    private Postoffice() {
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int v = s.nextInt();
        int p = s.nextInt();
        int[] villages = new int[v];
        for (int index = 0; index < v; index++) {
            villages[index] = s.nextInt();
        }
        for (int post : solve(villages, p)) {
            System.out.println(post + " ");
        }
    }

    /**
     * 求解
     * @param villages 村庄坐标
     * @param p        邮局个数
     * @return postoffices 按升序排列的邮局坐标
     */
    public static int[] solve(int[] villages, int p) {
        Arrays.sort(villages);
        int v = villages.length;

        //对于p<=2时,特殊处理
        if (p <= 2) {
            return solveX(villages, p);
        }

        //simple[i][j] 表示从村庄i到j(包括i,j)中放置一个邮局时这些村庄要走的路程
        int[][] simple = new int[v][v];
        for (int i = 0; i < v; i++) {
            for (int j = i; j < v; j++) {
                //此时,将邮局修在中间那个村庄可以得到最小路程
                int pos = (i + j) / 2;
                for (int k = i; k <= j; k++) {
                    simple[i][j] += k <= pos ? villages[pos] - villages[k] : villages[k] - villages[pos];
                }
            }
        }

        //min[i][j] 表示在villages[0...i-1]中修建j个邮局时最小的路程
        int[][] min = new int[v + 1][p + 1];
        //trace[i][j] 表示这j个邮局中最后一个邮局影响村庄的起始位置
        int[][] trace = new int[v + 1][p + 1];
        for (int i = 1; i <= v; i++) {
            min[i][1] = simple[0][i - 1];
        }
        for (int j = 2; j <= p; j++) {
            for (int i = j; i <= v; i++) {
                min[i][j] = Integer.MAX_VALUE;
                for (int k = j - 1; k <= i - 1; k++) {
                    if (min[i][j] > min[k][j - 1] + simple[k][i - 1]) {
                        min[i][j] = min[k][j - 1] + simple[k][i - 1];
                        trace[i][j] = k;
                    }
                }
            }
        }
        int[] postoffices = new int[p];
        int end = v - 1;
        for (int index = p - 1; index >= 0; index--) {
            int begin = trace[end + 1][index + 1];
            postoffices[index] = villages[(begin + end) / 2];
            end = begin - 1;
        }
        return postoffices;
    }

    /**
     * 对邮局个数为1或2时的处理
     * 此时对应的时间复杂度为O(1) 与O(n*n)
     */
    private static int[] solveX(int[] villages, int p) {
        int v = villages.length;
        if (p == 1) {
            return new int[]{villages[(v - 1) / 2]};
        } else {
            int pos = 0;
            int min = Integer.MAX_VALUE;
            for (int index = 0; index < v - 1; index++) {
                int p1 = index / 2;
                int p2 = (index + v) / 2;
                int tmp = 0;
                for (int k = 0; k < v; k++) {
                    if (k <= index) {
                        tmp += k <= p1 ? villages[p1] - villages[k] : villages[k] - villages[p1];
                    } else {
                        tmp += k <= p2 ? villages[p2] - villages[k] : villages[k] - villages[p2];
                    }
                }
                if (tmp < min) {
                    min = tmp;
                    pos = index;
                }
            }
            return new int[]{villages[pos / 2], villages[(pos + v) / 2]};
        }
    }
}