牛客网 2018年全国多校算法寒假训练营练习比赛（第四场） C.求交集-白红宇

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

阅读量：4610 次

发布时间：2019-06-09

本文共 1307 字，大约阅读时间需要 4 分钟。

C.求交集

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

链接：

来源：牛客网

题目描述

给你两个升序排列的集合，求出两个集合的交集。

输入描述:

有多个测试用例，输入到文件结束。 对于每一个测试用例： 第一行输入两个整数n,m(0
      
       <=1000000),分别代表第一个集合和第二个集合的元素的数量。 第二行输入n个整数，表示第一个集合中的元素，元素之间用空格隔开。 第三行输入m个整数，表示第二个集合中的元素，元素之间用空格隔开。 两个集合中的元素范围在[-1000000000,1000000000]区间内。

输出描述:

每个测试用例用一行来输出两个集合的交集的所有元素（元素用空格隔开且按升序排列），若交集为空则输出"empty"。

示例1

输入

2 31 31 2 3

输出

1 3

备注:

交集为空的情况下，输出"empty"。

这个题因为直接就是升序排列的，直接暴力就可以。

代码:

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #include
            
              9 #include
             
              10 #include
              
               11 using namespace std;12 typedef long long ll;13 const int maxn=1e6+5;14 const double eps=1e-6;15 const int inf=1<<30;16 const int mod=1e8; 17 ll a[maxn],b[maxn],c[maxn]; 18 int main(){ 19 int n,m,k; 20 ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 21 while(cin>>n>>m){ 22 int cnt=0,l1=1,l2=1; 23 for(int i=1;i<=n;i++) cin>>a[i]; 24 for(int i=1;i<=m;i++) cin>>b[i]; 25 while(1){ 26 if(l1==(n+1)||l2==(m+1))break; 27 if(a[l1]>b[l2]) l2++; 28 else if(a[l1]==b[l2]){ 29 c[++cnt]=a[l1]; 30 l1++;l2++; 31 } 32 else l1++; 33 } 34 if(cnt==0) cout<<"empty"<