程序填空题：The Turnpike Reconstruction Problem

Suppose we are given $n$ points $p_1, p_2, ... p_n$ located on the $x$-axis. $x_i$ is the $x$-coordinate of $p_i$. Let us further assume that $x_1=0$, and the points are given from left to right. These $n$ points determine $\frac{n(n-1)}{2}$ (not-necessarily unique) distances $d_1, d_2, ... d_{n(n-1)/2}$ between every pair of points of the form $|x_i-x_j|$ ($i \neq j$).

The *Turnpike reconstruction problem* is to reconstruct a point set from the distances.

This algorithm is to read the number $n$ and $\frac{n(n-1)}{2}$ distances $d_i$, then print one valid sequence of points $p_i$. Please complete the following program.

```c++
#include
#include
const int MAXN = 1000, MAXD = MAXN * (MAXN - 1) / 2;
int p[MAXN], d[MAXD], n, m;
int id[MAXD];
bool used[MAXD];
int binary_search(int x, int m) {
int l = 0, r = m;
while (l < r) {
int mid = (l + r) / 2;
if (d[mid] < x || (d[mid] == x && used[mid]))
;
else
r = mid;
}
return l;
}
bool recursive(int now, int top, int m) {
int i;
for (i = 0; i < now; i++) {
id[top + i] = binary_search(abs(p[i] - p[now]), m);
if( && !used[id[top + i]])
used[id[top + i]] = true;
else break;
}
if (i == now) {
if (now == n - 1)
return true;
while (used[m - 1])
m--;
p[now + 1] = d[m - 1];
if (recursive(now + 1, top + now, m))
return true;
if (now <= 1)
return false;
p[now + 1] = ;
if (recursive(now + 1, top + now, m))
return true;
}
for(int j = 0; j < i; j++)
;
return false;
}
int main()
{
scanf("%d", &n);
m = n * (n - 1) / 2;
for (int i = 0; i < m; i++)
scanf("%d", &d[i]);
std::sort(d, d + m);
p[0] = 0;
if (!recursive()) {
puts("NO ANSWER");
return 0;
}
std::sort(p, p + n);
for (int i = 0; i < n; i++)
printf("%d\n", p[i]);
return 0;
}
```






答案：
第1空：l = mid + 1

第2空：d[id[top + i]] == abs(p[i] - p[now])

第3空：p[1] - d[m - 1]

第4空：used[id[top + j]] = false

第5空：0, 0, m