2018年全国多校算法寒假训练营练习比赛（第四场）C-求交集

链接：https://www.nowcoder.com/acm/contest/76/C 来源：牛客网 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述  给你两个升序排列的集合，求出两个集合的交集。 输入描述: 有多个测试用例，输入到文件结束。 对于每一个测试用例： 第一行输入两个整数n,m(0<n,m<=1000000),分别代表第一个集合和第二个集合的元素的数量。 第二行输入n个整数，表示第一个集合中的元素，元素之间用空格隔开。 第三行输入m个整数，表示第二个集合中的元素，元素之间用空格隔开。 两个集合中的元素范围在[-1000000000,1000000000]区间内。 输出描述: 每个测试用例用一行来输出两个集合的交集的所有元素（元素用空格隔开且按升序排列），若交集为空则输出"empty"。 示例1 输入 2 3 1 3 1 2 3 输出 1 3 备注: 交集为空的情况下，输出"empty"

。

题意：多组数据。给出两个长度（不等）和两行序列，求交集。

思路：想到严蔚敏数据结构书上一段伪代码，大致是去重合并两个数组。这题就时这么做，写题解的原因是，一开始用cin老是超时，还以为有特殊情况没有考虑，原来真的是超时啊！

解决方案：1. 不把结果存在第三个数组中，而是直接输出。最后一个数后面不跟空格，也可以处理。

                2. 放弃cin专用scanf

                3. 加上一段

std::ios::sync_with_stdio(false); cin.tie(0);

给输入流加速，好像是因为关闭了了c++对c输入输出的兼容性，具体原理不太清楚，如果以后再见再查。

代码：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #define INF 0x3f3f3f3f typedef long long ll; using namespace std; const int maxm = 1e6+10; int n, m, a[maxm], b[maxm], c[maxm]; int main() { std::ios::sync_with_stdio(false); cin.tie(0); while(cin >> n >> m){ for(int i = 0; i < n; i++){ cin >> a[i]; } for(int i = 0; i < m; i++){ cin >> b[i]; } int p1 = 0, p2 = 0, p3 = 0; while(p1 < n && p2 < m){ if(a[p1] == b[p2]){ c[p3++] = a[p1]; p1++;p2++; } else if(a[p1] < b[p2]){ p1++; } else if(b[p2] < a[p1]){ p2++; } } if(p3 > 0){ for(int i = 0; i < p3-1; i++){ cout << c[i] << " "; } cout << c[p3-1] << endl; } else{ cout << "empty" << endl; } } return 0; }