首页 > 代码库 > 《数据结构与算法分析：C语言描述》复习——第十章“算法设计技巧”——收费站重建问题
《数据结构与算法分析：C语言描述》复习——第十章“算法设计技巧”——收费站重建问题
2014.07.07 18:19
简介：
给定一条数轴上的n个互不重合的点，你可以计算出C(n,2)=n(n-1)/2个距离。如果我给你这些距离值，你能反推出这n个点的坐标吗？
描述：
首先，考虑到你可以平移这n个点，并且可以左右反转它们得到对称的两种情况，我们不妨假设最靠左的点p0的坐标正好是0。
接下来我们通过深度优先搜索和回溯的手段逐个求出每个点的坐标。
起初我们有n(n-1)/2个距离，搜索要如何下手呢？从最长的那个下手。
比如n=3时，有距离之{3,7,10}。这其中，10能够告诉我们最靠右的点p2坐标一定10，因为两端的两点离得最远。
由此我们一开始就能够确定两个端点的坐标p0（人为规定为0）和pn-1，接下来中间的n-2个点需要通过搜索来确定。
假设你现在已经确定了i个点的坐标，剩余的距离集合是D余（想想当你确定了i个点之后，手里剩下还有多少个距离）。初始的距离集合D全拥有n(n-1)/2个距离。
如果目前D余中最大的距离是d=max(D余)，那么第i+1个点的坐标可能是d或者pn-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 }