程序填空题：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