找规律
首先根据题意,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;
}