题目链接（洛谷）
题目大意
众所周知，从$n$个非负整数中任取两个相加共有$\frac{n\times (n-1)}{2}$个和。现在给出这$\frac{n\times (n-1)}{2}$个和值，要求$n$个非负整数。若答案不存在，输出“impossible”。
$n \le 10$，给出的数$\le10^5$
分析
设第$i$个非负整数为$a_i$，不妨设$a_1\le a_2\le …\le a_n$。我们将$\frac{n\times (n-1)}{2}$个和写成如下形式：
在同一行内，值从左到右递增；在同一列内，值从上到下递增。显然，左上角的值就是所有和里的最小值。若$a_1$已知，我们可以找到最小值，求出$a_2$；之后把这一列的元素删光，再次求最小值（此时是$a_1+a_3$），求出$a_3$，并删光这一列的元素，再找最小值（此时是$a_1+a_4$）……这样可以推出$a_1\to a_n$所有值。
如何求$a_1$的值？考虑最小值就是$a_1+a_2$，且$a_1\le a_2$, 从$0\to$最小值的$\frac{1}{2}$枚举即可。如果给出的集合中值没有枚举的$a_1$推出来的值，那么枚举的值是不合法的。
要快速删除数列的元素、求最小值、判断元素存不存在，使用$\text{multiset}$实现。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 15;
ll n, a, ans[N];
bool ex;
multiset<ll> s, t;
multiset<ll>::iterator it;
bool check(ll a_1) {
t = s;
ans[1] = a_1;
for (int i = 2; i <= n; i++) {
ans[i] = *t.begin() - a_1;
for (int j = 1; j < i; j++) {
it = t.find(ans[i] + ans[j]);
if (it == t.end()) return false;
t.erase(it);
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
while (cin >> n) {
ex = false;
s.clear();
for (int i = 1; i <= n * (n - 1) / 2; i++) {
cin >> a;
s.insert(a);
}
for (ll i = 0; i <= *s.begin() / 2; i++) {
if (check(i)) {
for (int j = 1; j <= n; j++) cout << ans[j] << " ";
cout << endl;
ex = true;
break;
}
}
if (!ex) cout << "Impossible" << endl;
}
return 0;
}
|