立志用最少的代码做最高效的表达

---

PAT甲级最优题解——>传送门

---

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

---

题意： 分两行输入两个序列， 每行第一个数n为序列个数。 将两个序列求并集，非降序排序，求中位数。 如果序列数为偶数，则输出左侧的数。

分析：
解法一：定义优先队列，将两个序列数入队，输出中位数。
解法二：定义multiset(有序不去重集合)，输入，输出中位数。

注意：
如果采用cin、cout输入输出，需要取消流同步，即：ios::sync_with_stdio(false);。 速度相较于scanf、printf来说更快。

---

储备知识扩展(很重要，提高效率，降低码量)：

• set——有序去重集合。

• map——有序去重映射

• multiset——有序不去重集合

• multimap——有序不去重映射

• unordered_set——无序不去重集合(普通集合)

• unordered_map——无序不去重映射(普通映射)

---

解法一：优先队列

#include<bits/stdc++.h> using namespace std; using gg = long long; int main() {ios::sync_with_stdio(false);//升序优先队列(越大则优先级越高) priority_queue<gg, vector<gg>, greater<gg> >q;gg len = 0; //集合长度 for(gg i = 0; i < 2; i++) {gg n; cin >> n; len += n;while(n--) {gg x; cin >> x; q.push(x); } } int last = (len+1)/2-1;for(int i = 0; i < last; i++) q.pop();cout << q.top();return 0; }

耗时：

---

解法二：multiset集合

#include<bits/stdc++.h> using namespace std; using gg = long long; int main() {ios::sync_with_stdio(false);multiset<gg>m;gg len = 0;for(gg i = 0; i < 2; i++) {gg n; cin >> n; len += n;while(n--) {gg x; cin >> x; m.insert(x); } } gg i = 0, last = (len+1)/2-1;for(auto um : m) if(i++ == last) { cout << um; break; }return 0; }

耗时(比起优先队列高了一些，因为集合每次插入元素的复杂度都为O(nlogn))：

---

痛苦难道是白忍受的吗？他应该使我们伟大！      ——托马斯·曼

总结

以上是生活随笔为你收集整理的【19行代码AC,简洁】1029 Median (25 分)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。