### 题目 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. **Input Specification:** Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (≤2×10^​5^) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of **long int**. **Output Specification:** For each test case you should output the median of the two given sequences in a line. **Sample Input:** 4 11 12 13 14 5 9 10 15 16 17 **Sample Output:** 13 ### 题目解读 首先，给出递增序列中位数的定义，奇数个元素不用多说，就是最中间那个；对于偶数个元素，比如 `1 2 3 4`，定义`2`是中位数（平常可能会`（2+3）/ 2`，这里不是）。 两行输入，每一行第一个数字`n`是序列个数，后面是`n`个数字的递增序列。 要求输出这两个递增序列合并后的序列的中位数。 **补**：虽然题目说数组元素范围不超过`long int`，但其实我试了一下用`int`就可以了。 ### 思路解析 - 关于两个递增序列合并的问题我就不多说了，无非就是++每次比较两个序列当前元素，选择较小的那个放入新的序列，然后被选取的那个序列的指针和最后得到的序列的指针顺序后移一位++。大体框架是这样的： ```cpp while (i < n && j < m) { c[k++] = a[i] < b[j] ? a[i++] : b[j++]; } if (i < n) { while (i < n) { c[k++] = a[i++]; } } else if (j < m) { while (j < m) { c[k++] = b[j++]; } } ``` - 然后就是中位数的选择问题，一共有 `n + m` 个元素，最中间的那个就是**第** `（n + m + 1）/ 2`**个**数字，为什么要加`1`，比如 `1 2 3 4 5 6 7，7 / 2 = 3`，但是`4`是中位数，`4`是**第**四个元素，当然你如果要按下标来说的话，`4`的**下标**的确是`3`，不用加1再除以2. - 第一种思路就是创建第三个数组`c[a.size()+b.size()]`，按照我上面写的代码把`a[]`和`b[]`顺序合并到`c`中，然后输出`c`的中位数`（c[(m+n)/2]）`。但是这种方式提交后最后一个测试点是**运行超时**，其实是**内存溢出**了。 - 我们考虑一下，首先，假如**第**`mid`个数字是`c[]`的中位数，那么我们是不需要`c[]`中`mid`之后的写那些数字，那么我们在合并`a`和`b`的时候，记录一下当前合并了几个数字，**当合并到第`mid`个数时就退出`while`**；那么关于`mid`前面的那些元素我们也是不需要保存的，我们只需要一个变量，每次它都被赋值为`a[]`和`b[]`中当前最小的那个，当合并到`第mid次`时，这个变量就是我们需要的中位数。 ```cpp while (i < n && j < m) { // 每次找a和b当前位置小的那个那个元素 res = a[i] < b[j] ? a[i++] : b[j++]; // 得到了mid个就退出 if (++cnt == mid) break; } ``` - 这里有**两个问题**：第一个是这个`mid`的取值，还记得我们上面那个`1234567`的例子吗，我们这里是**按照当前统计到第几个数字了来记录**的，中位数是第`4`个，所以 `mid =（n+m+1）/2;` 第二个问题是：如果a和b中一个特别短呢？比如 `a[] : 2，b[] : 1 3 5 7`。这样的话`while`退出就可能是`a`和`b`中某个数组合并完了，但是还没达到第`mid`个，就拿这个例子来说，到`while`退出时，我们应该是先选择1，再选择2，然后a合并完了，while退出了，但此**时我们的`cnt`只记录到`2`，所以我们还差`mid-cnt`个数字，所以我们应该去`b`里面继续向后推进m`id-cnt`个位置，得到中位数**。 ```cpp // while退出后 if (cnt < mid) { // b[]数组全部元素合并过了不够mid个，已经得到了cnt个，还差 mid - cnt个 // 应该在a[]第i个的基础上向后移mid - cnt个位置，但是 【第几个】 和 【下标】 之间是差了个1的。 if (i < n) res = a[i + mid - cnt - 1]; else res = b[j + mid - cnt - 1]; } ``` ### 注意事项（重点） - 不要用三个数组，`a[200000]，b[200000]，c[400000]`，会内存溢出。 - 注意数组【第几个】元素与【下标】之间是差了个`1`的，实在不知道要不要`加1`或`减1`就写个例子试一下。 - 不要用`cin`输入，亲测，最后一个测试点依然是运行超时。 #### 最终代码 ```cpp #include using namespace std; // 定义三个数组会溢出 // 用cin会溢出 int main() { int n, m, i, j, res, cnt, mid, a[200000], b[200000]; // 第一组有n个数 // cin >> n; scanf("%d", &n); // for (i = 0; i < n; ++i) cin >> a[i]; for (i = 0; i < n; ++i) scanf("%d", &a[i]); // cin >> m; scanf("%d", &m); // 第二组有m个数 // for (j = 0; j < m; ++j) cin >> b[j]; for (j = 0; j < m; ++j) scanf("%d", &a[j]); // 合起来的一半有 假如 7 个 1 2 3 4 5 6 7，中位数是4，第4个数字 mid = (n + m + 1) / 2; // cnt 得到第几个数 i = 0; j = 0, cnt = 0; while (i < n && j < m) { // 每次找a和b当前位置小的那个那个元素 res = a[i] < b[j] ? a[i++] : b[j++]; // 得到了mid个就退出 if (++cnt == mid) break; } // 判断退出条件 if (cnt < mid) { // b[]数组全部元素合并过了不够mid个，已经得到了cnt个，还差 mid - cnt个 // 应该在a[]第i个的基础上向后移mid - cnt个位置，但是 【第几个】 和 【下标】 之间是差了个1的。 if (i < n) res = a[i + mid - cnt - 1]; else res = b[j + mid - cnt - 1]; } cout << res; return 0; } ```