求交集

链接：https://www.nowcoder.net/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”。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <queue>
 4 #include <cstdio>
 5 using namespace std;
 6 struct cmp
 7 {
 8     bool operator()(long long x, long long y)
 9     {
10         return x > y;
11     }
12 };
13 priority_queue<long long,vector<long long>,cmp>q, p;
14 int main()
15 {
16     int n, m;
17     while (~scanf("%d %d",&n,&m))
18     {
19         while (!q.empty()) q.pop();
20         while (!p.empty()) p.pop();
21         int i;
22         for (i = 1; i <= n; i++)
23         {
24             long long x;
25             scanf("%lld", &x);
26             q.push(x);
27         }
28         for (i = 1; i <= m; i++)
29         {
30             long long x;
31             scanf("%lld", &x);
32             p.push(x);
33         }
34         bool f = 0;
35         queue<long long>s;
36         while (!p.empty() && !q.empty())
37         {
38             while (!p.empty() && (q.top() > p.top()))
39             {
40                 p.pop();
41             }
42             while (!q.empty() && (q.top() < p.top()))
43             {
44                 q.pop();
45             }
46             if (q.top() == p.top())
47             {
48                 if(!s.empty())
49                 {
50                     cout << s.front() << " ";
51                     s.pop();
52                     s.push(q.top());
53                 }
54                 else
55                     s.push(q.top());
56                 q.pop();
57                 p.pop();
58                 f = 1;
59             }
60         }
61         if (f)
62         {
63             cout << s.front() << endl;
64         }
65         else  printf("empty
");
66     }
67     return 0;
68 }