《数据结构与算法分析：C语言描述》复习——第十章“算法设计技巧”——收费站重建问题

浏览数：31 / 时间：2015年06月08日

2014.07.07 18:19

简介：

　　给定一条数轴上的n个互不重合的点，你可以计算出C(n,2)=n(n-1)/2个距离。如果我给你这些距离值，你能反推出这n个点的坐标吗？

描述：

　　首先，考虑到你可以平移这n个点，并且可以左右反转它们得到对称的两种情况，我们不妨假设最靠左的点p₀的坐标正好是0。

　　接下来我们通过深度优先搜索和回溯的手段逐个求出每个点的坐标。

　　起初我们有n(n-1)/2个距离，搜索要如何下手呢？从最长的那个下手。

　　比如n=3时，有距离之{3,7,10}。这其中，10能够告诉我们最靠右的点p₂坐标一定10，因为两端的两点离得最远。

　　由此我们一开始就能够确定两个端点的坐标p₀（人为规定为0）和p_n-1，接下来中间的n-2个点需要通过搜索来确定。

　　假设你现在已经确定了i个点的坐标，剩余的距离集合是D_余（想想当你确定了i个点之后，手里剩下还有多少个距离）。初始的距离集合D_全拥有n(n-1)/2个距离。

　　如果目前D_余中最大的距离是d=max(D_余)，那么第i+1个点的坐标可能是d或者p_n-1-d。

　　这样产生了两种可能性，对于每一种可能性，你都要第i+1个点与前i个点的距离是否能在D余中找到。

　　如果D余中找不到对应的距离值，说明这次搜索已经失败，需要回溯到上层。

　　而如果这i次检验全部成功的话，需要从D_余中去掉i个距离值。

　　这个搜索与回溯的过程说起来容易，但如果你真的用简单的数组作为数据结构，会发现操作很不方便而且效率低下。

　　我们有如下三点需求：

　　　　1. 找出D_余中最长的边，我需要有序的数据

　　　　2. 查找某个距离值d是否在D_余中，我需要快速查找（至少不是线性查找）

　　　　3. 回溯时我需要把去掉过的距离值重新放回D_余中，我需要快速插入（向数组中间插入元素，效率无法忍受）

　　基于以上三点需求，平衡树成了最佳选择。于是STL的<map>成为解决这个问题的上佳工具。（begin()与rbegin()有何用处？）

　　就算你执意用简单的数组解决这个问题，觉得那样可以偷懒，实际写起来还是既繁琐又低效。（因为往数组中间插入或删除东西实在是很不和谐的操作）

　　说到时间复杂度，这种搜索+回溯的解法自然是指数级的。

　　也许用八皇后问题来作为回溯的例子更容易些，不过既然作者选了这个我们就学这个吧。

实现：

  1 // Turnpike reconstruction problem.
  2 //    Description:
  3 //        Given n * (n - 1) / 2 distances, find out if you can determine the 
  4 //            relative coordinates of n points.
  5 #include <algorithm>
  6 #include <cmath>
  7 #include <iostream>
  8 #include <map>
  9 #include <vector>
 10 using namespace std;
 11 
 12 int myabs(int x)
 13 {
 14     return x > 0 ? x : -x;
 15 }
 16 
 17 bool turnpikeReconstruction(int idx, vector<int> &x, map<int, int> &dist_set, 
 18     const int far)
 19 {
 20     if (idx == 0) {
 21         return true;
 22     }
 23     
 24     int cur_n;
 25     int cur_far;
 26     int i;
 27     map<int, int>::iterator it;
 28     
 29     cur_n = (int)x.size();
 30     cur_far = dist_set.rbegin()->first;
 31     for (i = 0; i < cur_n; ++i) {
 32         it = dist_set.find(myabs(cur_far - x[i]));
 33         if (it == dist_set.end() || it->second == 0) {
 34             break;
 35         }
 36         --it->second;
 37         if (it->second == 0) {
 38             dist_set.erase(it);
 39         }
 40     }
 41     if (i == cur_n) {
 42         x.push_back(cur_far);
 43         if (turnpikeReconstruction(idx - 1, x, dist_set, far)) {
 44             return true;
 45         }
 46         x.pop_back();
 47     }
 48     cur_n = i;
 49     for (i = 0; i < cur_n; ++i) {
 50         ++dist_set[myabs(cur_far - x[i])];
 51     }
 52     
 53     cur_n = (int)x.size();
 54     cur_far = dist_set.rbegin()->first;
 55     for (i = 0; i < cur_n; ++i) {
 56         it = dist_set.find(myabs(far - cur_far - x[i]));
 57         if (it == dist_set.end() || it->second == 0) {
 58             break;
 59         }
 60         --it->second;
 61         if (it->second == 0) {
 62             dist_set.erase(it);
 63         }
 64     }
 65     if (i == cur_n) {
 66         x.push_back(far - cur_far);
 67         if (turnpikeReconstruction(idx - 1, x, dist_set, far)) {
 68             return true;
 69         }
 70         x.pop_back();
 71     }
 72     cur_n = i;
 73     for (i = 0; i < cur_n; ++i) {
 74         ++dist_set[myabs(far - cur_far - x[i])];
 75     }
 76     
 77     return false;
 78 }
 79 
 80 int main()
 81 {
 82     int i;
 83     int n, n2;
 84     vector<int> x;
 85     int dist;
 86     map<int, int> dist_set;
 87     int far;
 88     
 89     while (cin >> n2 && n2 > 0) {
 90         for (i = 0; i < n2; ++i) {
 91             cin >> dist;
 92             ++dist_set[dist];
 93         }
 94         n = (int)sqrt(n2 * 2.0) + 1;
 95         far = dist_set.rbegin()->first;
 96         --dist_set[far];
 97         if (dist_set.rbegin()->second == 0) {
 98             dist_set.erase(far);
 99         }
100         
101         x.push_back(0);
102         x.push_back(far);
103         if (!turnpikeReconstruction(n - 2, x, dist_set, far)) {
104             cout << "No solution." << endl;
105         } else {
106             sort(x.begin(), x.end());
107             for (i = 0; i < n; ++i) {
108                 cout << x[i] << ‘ ‘;
109             }
110             cout << endl;
111         }
112         
113         x.clear();
114         dist_set.clear();
115     }
116     
117     return 0;
118 }