C. Assembly via Minimums

发布时间 2023-10-02 21:38:32作者: 不o凡

C. Assembly via Minimums

找规律
首先根据题意,B组数据的顺序是完全没有关系的,因为可以随意打乱,所以a组的值一定在b组里找,这不是废话
其次我们观察数据可知,最小值出现的次数是n-1,比较好理解的方法是:分别把最小值放在开头和结尾,因为要取最小值所以在B组出现的次数一定是n-1。
接着我们推理次小值一定出现n-2次,把次小值放在第二个位置完全成立。
为了使推理成立,我们可以制造a组的值是从小到大,或者从大到小,这样我们的推理就完全成立。
a的最小值就是出现n-1次的值,最大值就是出现1次或零次的值(或者说是大于等于b组的最大值)

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
int q[N];
void solve() {
	priority_queue<int> q;//这里用优先队列存储
	int n;
	cin >> n;
	int m = n * (n - 1) / 2;
	for (int i = 1; i <= m; i++) {
		int x;
		cin >> x;
		q.push(-x);//从小到大升序,因为优先队列默认是大根堆,也就是从大到小排序,取-就从小到大了
	}
	vector<int> ans(n+1);
	for (int i = n - 1;i>=1; i--) {
		int t = i;
		ans[i] = -q.top();//记录最小值
		while (t--) {//去重
			q.pop();
		}
	}
	cout << ans[1]<<' ';//先输出最大值,值>=ans[1]就行
	for (int i = 1; i < n; i++) cout << ans[i]<<' ';
	cout << '\n';
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}