Luogu1286 两数之和

Link

Sol

先对给你的这个数组排序，我们设排完序后的数组为a[1],a[2],\dots,a[n]，给你的数组升序排序后是b[1],b[2],\dots,b[n * (n-1) /2]

考虑b[1]是怎么被a[]相加而得的，因为b[1]是b中最小的元素，那么b[1]=a[1]+a[2]

第二小的b[2]=a[1] + a[3]

由a[2]开始往后相加的元素一定在b[x] = a[1]+a[k]开始，这样的b[x]我们只需要O(n)的枚举找到就可以了

做法就出来了

每次找到a[k]这个元素，把a[1]+a[2], a[1]+a[3],\dots,a[1]+a[k]这些元素找出来，再把他们在b中去掉，再从a[2]开始，以此类推

时间复杂度O(n^3)

Code

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

#define int long long

const int SIZE = 1e7 + 5;

int n, m, cnt;
int a[SIZE], b[SIZE];

std::multiset < int > s;
std::vector < vector < int > > ans;

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void solve(int p)
{
    if ((a[1] + a[2] + a[p]) & 1) return;
    b[1] = (a[1] + a[2] + a[p]) / 2 - a[p];
    b[2] = a[1] - b[1], b[3] = a[2] - b[1];
    if (b[1] <= 0) return;
    s.clear();
    for (int i = 3; i <= m; ++ i) {
        if (i != p) s.insert(a[i]);
    }
    for (int i = 4; i <= n; ++ i) { 
        b[i] = *s.begin() - b[1];
        s.erase(s.begin());
        for (int j = 2; j < i; ++ j) {
            auto it = s.find(b[i] + b[j]);
            if (it == s.end()) return;
            s.erase(it);
        }
    }
    std::vector < int > tmp;
    for (int i = 1; i <= n; ++ i) tmp.push_back(b[i]);
    ans.push_back(tmp);
    return;
}

inline int cmp(vector < int > &a, vector < int > &b) 
{
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i]) continue;
        return a[i] > b[i];
    }
}

signed main()
{
    while (std::cin >> n) {
        m = n * (n - 1) / 2;
        for (int i = 1; i <= m; ++ i) a[i] = read();
        std::sort(a + 1, a + m + 1);
        for (int i = 3; i <= m; ++ i) {
            if (i == 3 || a[i] != a[i - 1]) solve(i);
        }
        if (!ans.size()) {
            ans.clear();
            puts("Impossible");
            continue;
        }
        std::sort(ans.begin(), ans.end(), cmp);
        for (int i = 0; i < ans.size(); ++ i) {
            for (int j = 0; j < n; ++ j) printf("%d ", ans[i][j]);
            puts("");
        }
        ans.clear();
    }
    return 0;
}