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;
}
Comments | NOTHING