摘要
Title: A1029 Median
Tag: 二路归并
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

A1029 Median

• 题意

  Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1 = { 11, 12, 13, 14 } is 12, and the median of S2 = { 9, 10, 15, 16, 17 } is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.
  Given two increasing sequences of integers, you are asked to find their median.

• 思路

  二路归并

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2023-01-07 17:59:31
  * @FilePath: \GPLT\A1029\A1029.cpp
  * @LastEditTime: 2023-01-07 18:04:48
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define N n + 100
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(nullptr);                                                                                                  \
      cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  // #undef N
  // const int N = 1e5 + 10;
  
  // #undef int
  
  signed main()
  {
      IOS;
      int n, m;
      cin >> n;
      vector<int> a(n);
      for (int i = 0; i < n; ++i)
          cin >> a[i];
      cin >> m;
      vector<int> b(m);
      for (int i = 0; i < m; ++i)
          cin >> b[i];
  
      vector<int> c;
      int i = 0, j = 0;
      while (i < n || j < m)
      {
          if (j == m || (i < n && a[i] < b[j]))
              c.push_back(a[i++]);
          else
              c.push_back(b[j++]);
      }
      int sz = SZ(c);
      cout << c[(sz + 1) / 2 - 1] << '\n';
  
      return 0;
  }