【题解】P1286 两数之和

发表于 分类于 阅读次数： Valine：

题目链接（洛谷）

题目大意

众所周知，从\(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}\)个和写成如下形式：

\[ \begin{aligned} a_1+a_2~~a_1+a_3~~a_1+a_4~~a_1+a_5~~a_1+a_6~~&...~~a_1+a_n \\ a_2+a_3~~a_2+a_4~~a_2+a_5~~a_2+a_6~~&...~~a_2+a_n\\ a_3+a_4~~a_3+a_5~~a_3+a_6~~&...~~a_3+a_n\\ a_4+a_5~~a_4+a_6~~&...~~a_4+a_n\\ a_5+a_6~~&...~~a_5+a_n\\ ~~&...~~\\ &~~a_{n-1}+a_n \end{aligned} \] 在同一行内，值从左到右递增；在同一列内，值从上到下递增。显然，左上角的值就是所有和里的最小值。若\(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;
}