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个数，从小到大输出所有被擦去的数字。

输入样例

1 3 5 7 8

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-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 */