首页 > 代码库 > 5月3日济南清北学堂随堂测试题目

5月3日济南清北学堂随堂测试题目

消失的数字(number)

Time Limit:1000ms   Memory Limit:128MB

 

题目描述

rsy拥有n个数,这n个数分别是a1,a2,…,an。

后来出现了一个熊孩子zhw,用橡皮擦去了其中若干个数字,并且打乱了剩下的数字。rsy赶到现场后只剩下了m个数字b1,b2,…,bm,她想知道哪些数字被擦去了。

现在你需要告诉rsy被擦去的n-m个数是什么。

 

 

输入格式(number.in)

    第一行一个数n,第二行n个数ai,表示一开始的数字。

    第三行一个数m,第四行m个数bi,表示被擦去后的数字。

 

输出格式(number.out)

    一行n-m个数,从小到大输出所有被擦去的数字。

 

输入样例

5

1 3 5 7 8

3

3 5 8

 

输出样例

1 7

 

数据范围

对于30%的数据n<=1000,ai与bi都是有序的。

对于60%的数据n<=100000,ai与bi都是有序的。

对于80%的数据n<=100000,ai,bi<=n。

对于100%的数据n<=100000,1<=ai,bi<=10^9。

 

思路见代码注释

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<iostream>
 5 using namespace std;
 6 int n,m,a[100001],b[100001];
 7 int main()
 8 {
 9     freopen("number.in","r",stdin);
10     freopen("number.out","w",stdout);
11 /*对于a数组的操作*/ 
12     scanf("%d",&n);
13     for(int i=0;i<n;++i)
14         scanf("%d",&a[i]);
15 /*对于b数组的操作*/
16     scanf("%d",&m);
17     for(int i=0;i<m;++i)
18         scanf("%d",&b[i]);
19 /*排序,why?*/ 
20     sort(a,a+n);
21     sort(b,b+m);
22 /*准备工作,先把n-m输出,注意head是0,因为我的读入*/ 
23 //    printf("%d\n",n-m);
24     int head=0;
25 /*核心部分*/
26     for(int i=0;i<n;++i)
27     {
28         if(a[i]!=b[head])
29             printf("%d ",a[i]);
30         else
31             head++;
32     }
33 /*比较a[i]是否等于b[head],如果不相同(被擦掉),那么直接输出a[i],否则head++。 
34   那么,为什么这样可以呢?
35   前面我们排好了顺序,那么a[i]如果不与b[head]相同的话,它一定被擦掉。
36   那么直接输出就好啦! 
37   ( ^_^ )
38 */    
39     fclose(stdin);
40     fclose(stdout);
41     return 0;
42 }
43 /*
44 10
45 1 22 2 2 3 3 3 333 6 7
46 3
47 6 3 3
48 */

 

5月3日济南清北学堂随堂测试题目