UVa 10332 The Absent Minded Professor

题目描述

给定 $N$（$3\le N\le 50$）个金属球，它们的实际重量未知。教授用天平测量了所有两两球之间的重量差（取绝对值，即大减小），得到 $(N\ast (N-1))/2$ 个正整数读数（小于 $10000$）。现在需要为每个球分配一个非负整数重量，使得这些重量两两差值的多重集合恰好等于给定的读数集合。若存在多解，则要求输出按升序排列的重量序列，并规定第一个重量（最小重量）必须为 $0$，且若存在镜像解（即把每个重量 $w$ 替换为 $M-w$，其中 $M$ 为最大重量），则优先输出字典序较小的那个（即优先尝试较大的中间点）。若无解，输出 "Incorrect Balance."。

输入包含多组测试数据，每组以 $N$ 开头，随后一行或多行包含 $C(N,2)$ 个正整数。输入以 $\text{EOF}$ 结束。

输入格式

每组测试数据第一行是一个整数 $N$（$3\le N\le 50$）。接下来在若干行内给出 $(N\ast (N-1))/2$ 个正整数（小于 $10000$），表示所有两两重量差的读数。输入可能跨多行，但总数固定。

输出格式

对于每组数据，若存在解，则在一行中输出 $N$ 个整数，按重量升序排列，且最小重量为 $0$。若不存在，则输出一行 "Incorrect Balance."。

样例

输入

3 1 2 3
3 1 2 2
6 1 2 2 2 3 3 3 4 5 5 5 6 7 8 10

输出

0 2 3
Incorrect Balance.
0 3 5 6 8 10

题目分析

本题本质上是一个一维点集重建问题（$\text{Turnpike Problem}$）：给定 $n$ 个点之间的所有两两距离（即距离多重集合），要求恢复出这些点在直线上的位置（坐标）。已知最小坐标为 $0$，且所有坐标均为非负整数。由于距离集合只给出所有无序点对的距离，而点与点之间的相对位置未给出，因此需要从距离信息中反推出点的坐标。

经典解法是回溯搜索（递归 + 剪枝）。因为 $N\le 50$，距离值不超过 $10000$，但组合数 $C(50,2)=1225$，搜索空间理论上很大，但实际可行的剪枝策略能保证在题目限制内高效运行。

关键观察：

• 最大距离 $\max D$ 必定等于最大坐标与最小坐标（$0$）之差，因此可以直接确定两个端点：$0$ 和 $M=\max D$。
• 剩余待确定的点都在 $(0,M)$ 之间。
• 每次从剩余距离集合中取出当前最大值 $d$，它必然对应某个尚未确定的点与已确定点集中的某个点之间的距离。由于已知已有点集，这个新点只可能有两种候选位置：
• 距离 $0$ 为 $d$，即坐标为 $d$；
• 距离 $M$ 为 $d$，即坐标为 $M-d$。
• 依次尝试这两种候选位置，并检查该候选点与所有已有点的距离是否均在剩余距离集合中出现（且数量足够）。若成功，则删除这些距离，将该点加入已有点集，继续递归。若失败则回溯。

这种回溯策略在多数情况下能快速找到解或无解。

解题思路

数据结构与预处理

回溯函数设计

定义 bool dfs(multiset<int>& ms, vector<int>& points)，其中：

• ms 为当前剩余的未匹配距离的多重集合；
• points 为当前已确定的坐标集合（升序未要求，但内部可无序）。

递归终止条件：当 points.size() == N 时，若 ms 为空则找到完整解；否则失败。

递归过程：

• 若 ms 为空但点数未满，则返回 false。
• 取 ms 中的最大值 d = *ms.rbegin()。
• 候选1：令 x = d。若 0 < x < maxVal 且 x 不在 points 中，则检查该候选点与所有已有点的距离是否都能在 ms 中找到足够的数量。具体做法：统计所需差值 abs(x – p) 的频次 need，然后检查 ms 中每个差值是否至少达到该频次。若满足，则从 ms 中删除这些差值，将 x 加入 points，递归调用 dfs。若递归成功则返回 true；否则恢复删除的差值并移除 x。
• 候选2：令 x = maxVal – d。若 x 与候选1不同且 0 < x < maxVal 且 x 不在 points 中，则进行同样的检查与递归。
• 若两种候选均失败，返回 false。

正确性说明

• 最大距离 maxVal 必对应端点 0 和 maxVal，这一确定是必然的，因为任意两点距离不可能超过 maxVal，且 maxVal 只能由最小和最大点产生。
• 每次取剩余距离中的最大值 d，在已有点集确定的情况下，该距离必定来自某个未确定点与某个已有点的距离。由于已有点集包含端点 0 和 maxVal，未确定点只能位于 $(0,maxVal)$ 内，因此它到 0 的距离为 d 或到 maxVal 的距离为 d，这两种情况恰好对应坐标 d 和 maxVal – d。若都不成立则无解。
• 递归枚举所有可能性，且通过数量检查保证不会错误地匹配距离，因此算法是完备的。

镜像解与输出顺序

题目要求输出“第一个”解，且规定最小重量为 $0$。镜像解是指将每个重量 $w$ 替换为 $M-w$（$M$ 为最大重量），此时距离集合不变。为了输出字典序较小的那个解，我们在回溯时优先尝试候选点 x = d（即较大的中间点），因为这样得到的点集更倾向于偏大，其镜像则偏小；由于我们固定了最小点为 $0$，优先尝试大的点会使最终序列的第二个元素较大，而镜像的第二个元素较小，所以优先尝试大的点会输出字典序较小的解。

复杂度分析

• 最坏情况下，递归深度为 $N-2$（除去两个端点），每次尝试两个分支，故搜索树规模为 $O(2^N)$，但实际剪枝（数量检查）会大幅减少。由于 $N\le 50$，理论上 $2^{50}$ 不可接受，但实际该问题的回溯在随机数据上表现良好，且 $N$ 较小时可接受，$N$ 较大时因距离值有限且重复多，剪枝更有效。
• 每次尝试需检查当前点与所有已有点的距离，复杂度 $O(|points|)$，并操作 multiset 的查找和删除，单次检查复杂度 $O(|points|\cdot \log C)$，其中 $C$ 为剩余距离个数。
• 整体时间复杂度依赖于实际数据，但在 $N\le 50$ 且距离值范围较小的条件下，可通过本题。

代码实现

// The Absent Minded Professor
// UVa ID: 10332
// Verdict: Accepted
// Submission Date: 2026-06-24
// UVa Run Time: 0.010s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

int N, maxVal;

bool inPoints(const vector<int>& points, int x) {
for (int p : points) if (p == x) return true;
return false;
}

bool dfs(multiset<int>& ms, vector<int>& points) {
if ((int)points.size() == N) return ms.empty();
if (ms.empty()) return false;

int d = *ms.rbegin(); // 当前最大剩余差值

// 候选点1：x = d（与0的距离为d）
if (d > 0 && d < maxVal && !inPoints(points, d)) {
map<int, int> need;
for (int p : points) need[abs(d – p)]++;
bool ok = true;
for (auto& kv : need)
if ((int)ms.count(kv.first) < kv.second) { ok = false; break; }
if (ok) {
for (auto& kv : need)
for (int i = 0; i < kv.second; ++i)
ms.erase(ms.find(kv.first));
points.push_back(d);
if (dfs(ms, points)) return true;
points.pop_back();
for (auto& kv : need)
for (int i = 0; i < kv.second; ++i)
ms.insert(kv.first);
}
}

// 候选点2：x = maxVal – d（与maxVal的距离为d）
int x2 = maxVal – d;
if (x2 != d && x2 > 0 && x2 < maxVal && !inPoints(points, x2)) {
map<int, int> need;
for (int p : points) need[abs(x2 – p)]++;
bool ok = true;
for (auto& kv : need)
if ((int)ms.count(kv.first) < kv.second) { ok = false; break; }
if (ok) {
for (auto& kv : need)
for (int i = 0; i < kv.second; ++i)
ms.erase(ms.find(kv.first));
points.push_back(x2);
if (dfs(ms, points)) return true;
points.pop_back();
for (auto& kv : need)
for (int i = 0; i < kv.second; ++i)
ms.insert(kv.first);
}
}

return false;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

while (cin >> N) {
int cnt = N * (N – 1) / 2;
vector<int> diffs(cnt);
for (int i = 0; i < cnt; ++i) cin >> diffs[i];

sort(diffs.begin(), diffs.end());
if (diffs.empty() || diffs[0] <= 0) {
cout << "Incorrect Balance.\\n";
continue;
}

maxVal = diffs.back();
multiset<int> ms(diffs.begin(), diffs.end());

// 删除最大差值（对应0和maxVal之间的距离）
auto it = ms.find(maxVal);
if (it == ms.end()) {
cout << "Incorrect Balance.\\n";
continue;
}
ms.erase(it);

vector<int> points = {0, maxVal};

if (dfs(ms, points)) {
sort(points.begin(), points.end());
for (int i = 0; i < N; ++i) {
if (i) cout << ' ';
cout << points[i];
}
cout << '\\n';
} else {
cout << "Incorrect Balance.\\n";
}
}
return 0;
}

总结

本题是一类经典的距离几何重建问题，核心解法是回溯搜索，借助多重集合管理剩余距离，并利用最大距离确定两端点，将候选点限制为两种可能，有效剪枝。关键技巧在于：

• 利用 std::multiset 维护距离的频次，便于检查与恢复。
• 通过预先排序和最大距离确定端点，减少搜索空间。
• 优先尝试较大的候选点以符合题目要求的输出顺序。

该解法在 $N\le 50$ 且距离值不超过 $10000$ 的限制下表现良好，能够高效求出解或判定无解。理解此类问题的回溯框架对于解决更一般的“从成对距离恢复点集”问题有借鉴意义。