P1631 序列合并

思路

思路一

题目要求的是二维的，太麻烦，所以我们可以将其用一维划分，将每一组都变成线性的，那线性的就很好求了，直接排序然后从前往后算即可，那么就可以将这 \(n\) 组合并，但如果是整个都算出来再合并就会是 \(O(n^2)\) 的，所以可以只记录当前的，那么对于当前的最小的状态，下一个状态要么是其它组的最小状态，要么是当前组的下一个状态，所以只要记录下一个状态即可，其它组的最小状态已经被加进去了。

code

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

const int MaxN = 100010;

struct S {
  int i, j, t;

  bool operator<(const S &j) const {
    return t > j.t;
  }
};

int a[MaxN], b[MaxN], n;
priority_queue<S> q;

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }  
  sort(a + 1, a + n + 1);
  sort(b + 1, b + n + 1);
  for (int i = 1; i <= n; i++) {
    q.push({1, i, a[1] + b[i]});
  }
  for (int i = 1; i <= n; i++) {
    S u = q.top();
    q.pop();
    cout << u.t << " ";
    q.push({u.i + 1, u.j, a[u.i + 1] + b[u.j]});
  } 
  return 0;
}

时空复杂度

时间：排序：\(O(nlogn)\) 枚举：\(O(n)\) 堆：\(O(logn)\)
空间：\(O(n)\)

思路2

如果是两个已经排好序的数列，那么当前最小值肯定是两个头，那下一个最小值呢？可以是之前就已经加入的值，也可以是两个数列中删掉一个头的情况，处理一下即可。

时空复杂度

时间：\(O(nlogn)\)
空间：\(O(n)\)