1029 Median (25 分)
第一个序列用vector存储起来，第二个序列读入时可同时处理（在线算法）。
需要得到的数（结果）是两个序列组合并后，处于下标(n+m-1)/2的数，所以for循环需要执行(n+m-1)/2次（每次确定一个数）。
最后输出s2[i-1]或者s2[(n+m-1)/2]即可。
注意此处的处理：
如果输入个数到达上限，且等到最后输入的一个数被选择之后，把t置为无穷，防止再次进入此段代码。
1 if (j >= s1.size() || t < s1[j]) { 2 s2[k++] = t; 3 if (s2i == m) {//只有最后一个数被选择之后才会符合此条if语句 4 t = INFINITE; 5 } 6 if (s2i < m) { 7 ++s2i; 8 cin >> t; 9 } 10 }
1 #pragma warning(disable:4996) 2 #define _CRT_SECURE_NO_WARNINGS 3 4 #include <iostream> 5 #include <algorithm> 6 #include <cmath> 7 #include <vector> 8 #include <map> 9 #include <set> 10 #include <unordered_set> 11 #include <unordered_map> 12 #include <queue> 13 #include <cmath> 14 #include <string> 15 #define INFINITE 2000000000 16 using namespace std; 17 18 19 int main() { 20 int n, m; 21 vector<long int> s1, s2; 22 cin >> n; 23 s1.resize(n); 24 for (int i = 0; i < n; ++i) { 25 cin >> s1[i]; 26 } 27 cin >> m; 28 int k = 0, j = 0; 29 s2.resize(n + m); 30 int i, t; 31 cin >> t; 32 int s2i = 1; 33 for (i = 0; i < (n + m + 1) / 2; ++i) { 34 if (j >= s1.size() || t < s1[j]) { 35 s2[k++] = t; 36 if (s2i == m) { 37 t = INFINITE; 38 } 39 if (s2i < m) { 40 ++s2i; 41 cin >> t; 42 } 43 } 44 else { 45 s2[k++] = s1[j++]; 46 } 47 } 48 cout << s2[i - 1]; 49 return 0; 50 }