方法1:
有点像剪枝。
\(i\)从\(1~n\)循环,\(j\)同理,如果\(a[i]+b[j]\)放不进去,那么\(a[i]+b[j+1]\)也放不进去
code
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int b[100005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
priority_queue<int> q;
stack<int> c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(q.size()<n||a[i]+b[j]<=q.top()) q.push(a[i]+b[j]);
else break;
}
while(q.size()>n)q.pop();
}
while(!q.empty())
{
c.push(q.top());
q.pop();
}
while(c.size())
{
cout<<c.top()<<" ";
c.pop();
}
return 0;
}
方法2:
有点像游戏机里的滚蛋,又有点像某dijk算法,滚出去一个,恰好排在它后面的一定是下一个最小的,滚进去。
code:
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int b[100005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
for(int i=1;i<=n;i++) q.push({a[i]+b[1],i,1});
while (n--) {
int sum = get<0>(q.top());
int x = get<1>(q.top());
int y = get<2>(q.top());
q.pop();
if (y + 1 <= n) { // 确保不会超出数组b的范围
q.push({a[x] + b[y + 1], x, y + 1});
}
cout << sum << " ";
}
return 0;
}