题目描述

【问题描述】

Gardon 昨天给小希布置了一道作业，即根据一张由不超过 5000 的 N(3<=N<=100)个正整数组成的数表两两相加得到 N*(N-1)/2 个和，然后再将它们排序。例如，如果数表里含有四个数 1，3，4，9，那么正确答案是 4，5，7，10，12，13。小希做完作业以后出去玩了一阵，可是下午回家时发现原来的那张数表不见了，好在她做出的答案还在，你能帮助她根据她的答案计算出原来的数表么？

【输入形式】

包含多组数据，每组数据以一个 N 开头，接下来的一行有按照大小顺序排列的 N*(N-1)/2 个数，是小希完成的答案。文件最后以一个 0 结束。
假设输入保证解的存在性和唯一性。

【输出形式】

对于每组数据，输出原来的数表。它们也应当是按照顺序排列的。

【样例输入】

4
4 5 7 10 12 13
4
5 6 7 8 9 10
0
【样例输出】

1 3 4 9
2 3 4 6

思路分析

分析可知，该有序序列的第一项为a1+a2，第二项为a2+a3，a1<=(a1+a2)/2，依次取a1可能的值，将a1存入数组b，确定a1后可求出a2，a2也存入数组b，再从该有序序列中删除数组b中已有元素的加法组合，得到一个新的有序序列，该新有序序列的第一项为a1+a3，重复上述过程，若最后有序序列长度为0，则b数组中储存的即为最后结果；否则重新选取a1的值并求解。

代码

#include <bits/stdc++.h>
using namespace std;
void Clear(int* x, int y){for(int k = 0; k < y; k++)x[k] = 0;
}
int main(){int n;while(cin >> n && n != 0){int len = n*(n - 1)/2, top;int a[len], b[n];for(int i = 0; i < len; i++)cin >> a[i];				int maxm = a[0] / 2, maxn = a[len - 1] + 1;		for(int may = 1; may <= maxm; may++){vector<int> result(a, a + len);top = 0;Clear(b, n);b[top++] = may;while(top < n){b[top++] = result[0] - may;for(int t = 0; t < top - 1; t++){int dele = b[t] + b[top - 1];auto it = find(result.begin(), result.end(), dele);if(it != result.end())*it = maxn;//以赋值操作代替删除}sort(result.begin(), result.end());}if(count(result.begin(), result.end(), maxn) == len)break;}for(int i = 0; i < n; i++)cout << b[i] << ' ';cout << '\n';}return 0;
}

如果对各位看官有帮助不妨留下一个点赞￣ω￣=。