Luogu1286 两数之和

tony102

2020 年 10 月 17 日

1703 次浏览

暂无评论

815字数

题解

[Link](https://www.luogu.com.cn/problem/P1286)

## 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
```cpp
#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;
}
```

最后修改：2021 年 08 月 20 日