题目链接:
第一时间想到的思路是将 \(a,b\) 数组中的 \(n^2\) 个和全部枚举并压入优先队列中,最后再输出前 \(n\) 个数,代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
priority_queue<int, vector<int>, greater<int> > p;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int x = a[i] + b[j];
p.push(x);
}
}
for (int i = 0; i < n; i++) {
cout << p.top() << " ";
p.pop();
}
return 0;
}
但这样的话由于 \(N\) 最大可取 \(10^5\),优先队列会内存超限
于是想到动态维护 \(n\) 个从小到大的和,用大根堆,先压满 \(n\) 个和,由于 \(a,b\) 均为单调不减的数列,如果新的和比当前堆顶元素还要大,说明接下来也一定比堆顶元素大,直接break掉从 \(a\) 数组的下一轮循环开始枚举;反之若新的和比当前堆顶元素小,则pop掉一个元素再加入当前这个新的元素,大根堆会自动将其排序。
以下是AC代码。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], res[N];
priority_queue<int> p;
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int x = a[i] + b[j];
if (p.size() < n) p.push(x);
else {
if (p.top() > x) {
p.pop();
p.push(x);
}
else break;//很重要,如去掉这行则会有三个点超时
}
}
}
for (int i = 0; i < n; i++) {
res[i] = p.top();
p.pop();
}
for (int i = n - 1; i >= 0; i--) cout << res[i] << " ";
return 0;
}
标签:10,int,合并,cin,pop,P1631,++,push,序列
From: https://www.cnblogs.com/pangyou3s/p/18014356