---

C. Assembly via Minimums

原创 于 2023-09-05 14:55:24 发布 · 粉丝可见 · 285 阅读 · 1 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132691921

题目：

样例：

cobol<br/>5<br/>3<br/>1 3 1<br/>2<br/>10<br/>4<br/>7 5 3 5 3 3<br/>5<br/>2 2 2 2 2 2 2 2 2 2<br/>5<br/>3 0 0 -2 0 -2 0 0 -2 -2<br/>

1 3 3 10 10 7 5 3 12 2 2 2 2 2 0 -2 0 3 5

思路：

数学思维题，构造算法，这里我们从样例中可以知道，可能的 数组 a 最后一个元素一定是最大的，其次，根据数学的思维，找出性质，当 一个 数列从小到达的排序能构造出 像 序列 b 的元素，其中我们要注意限制的可能序列 a 的个数

代码详解如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

inline void solve()
{
	int n;	//  数组 a 大小
	cin >> n;
	int m = n * (n - 1) / 2;	// 数组 b 的大小
	int b[m];	// 定义数组 b
	
	for(int i = 0;i < m;++i)
	{
		cin >> b[i];	
	}
	
	//排序 b 
	sort(b,b + m);
	
	//开始构造 a
	// 这里的 i += --n  是需要一个最大数
	// 使得 可能数组 a 取得最小数,而 --n 是因为去掉我们比较过后的
	for(int i = 0;i < m;i += --n)
	{
		cout << b[i] << ' ';
	}
	// 最后比较过后肯定还剩下一个元素，是作为最后比较的元素
	// 而这个元素应该无穷大,所以最后输出数据范围的最大值
	
	cout << 1000000000 << endl;
	
}


signed main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}

最后提交：