求助, 复杂度要怎么看??
查看原帖
求助, 复杂度要怎么看??
1403184
Lin_ZZ123楼主2024/12/11 14:32
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int> pq;
const int N = 100010;
int a[N], b[N];
int n;

void print(int x)
{
    if(x == 0) return;
    int y = pq.top(); pq.pop();
    print(x - 1);
    cout << y << ' '; 
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
        cin >> b[i];
    pq.push(a[n] + b[1]); //贪心的最大值
    for(int i = 1; i < n; i++) 
    {
        for(int j = 1; j <= n && a[i] + b[j] <= pq.top(); j++)
        {
            pq.push(a[i] + b[j]); 
            if(pq.size() == n + 1)
                pq.pop();
        }
    }
    print(n);
    return 0;
}
2024/12/11 14:32
加载中...