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;
}