《程序员》2007第八期之算法擂台

题目描述（手头没书，不知道有没有记错）：有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]};
        }
    }
}

评论

8 楼 Eastsun 2007-08-22  

哎，看来以后即便没有测试也不能说出来
也不是不想测试，没条件，这边网吧网速巨慢，实在没耐心去下个jdk。

7 楼 抛出异常的爱 2007-08-22  

rtdb 写道

这个帖为什么被投隐藏了？？

> 并没有测试

贯出毛病来了。。。。

6 楼 Eastsun 2007-08-21  

rtdb 写道

这个帖为什么被投隐藏了？？

> 并没有测试

晕，这种简单的DP算法，即便没有测试，我也有9成的把握可以一次写对。
而且这个主要讨论算法，DP算法已经给出状态描述与转移方程，这个才是核心部分，代码只是补充完备起见。

5 楼 rtdb 2007-08-21  

这个帖为什么被投隐藏了？？

> 并没有测试

4 楼 Eastsun 2007-08-20  

Readonly 写道

这个题目有点意思，和小时候做的求最短路程算术题有点类似，是不是有直接的数学解？
另外，实际上村庄分布都是2维的，扩展一下这个题目，输入是一组村庄的x|y坐标，就变得更有实际意义一些了。

对于p=1时确实有直接的结果，我代码中也用到了。
对于一般情况至少我没想到有直接的结论，而且应该也不会有线性时间复杂度的算法。

如果把题目扩展到二维情形，事实上变成一个图论问题了，而且这个时候还得给出两两村庄之间的关系（有直接连接的道路？路程？）

ps:这个帖为什么被投隐藏了？？

3 楼 realreal2000 2007-08-20  

我的思路是这样的不知道对不对，假设v=p那么，所有村庄都有一个邮局所以距离是0，所以当p减少1的时候就应该减去村庄之间距离最近的两个村庄任意一个的邮局，类推，减少2的时候找出所有村庄中路途最短的2条，查看然后除去2个村庄，类推。。。时间复杂度，首先对村庄距离排序，n2,然后取出节点，即可

2 楼 Readonly 2007-08-20  

这个题目有点意思，和小时候做的求最短路程算术题有点类似，是不是有直接的数学解？
另外，实际上村庄分布都是2维的，扩展一下这个题目，输入是一组村庄的x|y坐标，就变得更有实际意义一些了。

1 楼 walkandsing 2007-08-20  

用遗传算法也行