那么第一题首先非常水的一道题……
看一下题
数字(number)
Time Limit:1000ms Memory Limit:128MB
题目描述
LYK拥有n个数,这n个数分别是a1,a2,…,an。
有一天它做了一个梦,在梦里它的这n个数有部分被小偷偷走了,只剩下了m个数b1,b2,…,bm。它想知道有哪些数字被小偷偷走了!
LYK告诉你a和b的值,你需要从小到大的告诉LYK,哪些数字不见了!
输入格式(number.in)
第一行一个数n,第二行n个数ai,表示一开始的数字。
第三行一个数m,第四行m个数bi,表示剩下的数字。
输出格式(number.out)
一行n-m个数,从小到大输出所有被偷走的数字。
Sample Input
5
1 3 3 7 8
3
3 7 8
Sample Output
1 3
数据范围
对于30%的数据n<=1000,ai与bi都是从小到大有序的。
对于60%的数据n<=100000,ai与bi都是从小到大有序的。
对于80%的数据n<=100000,ai,bi<=n。
对于100%的数据n<=100000,1<=ai,bi<=10^9。
由于上午讲了离散化,于是自然想到有离散化先处理一下,然后每次对照每个出现的数的出现个数就可以了.
这里就不附上代码了
金牌爷讲的时候却没有用离散化……
他用的只是普通的数组操作
那么一样的读入,然后快排,因为是100000的数量上限所以快排没有问题。
然后就开始逐位比对,两个数组是要分开操作的,并不难,下面附上这种方法的代码。
#include<algorithm>
#include<iostream>
using namespace std;
int a[],b[];
int main() {
int n,m;
cin >> n;
for(int i=; i<=n; ++i)
cin >> a[i];
cin >> m;
for(int i=; i<=m; ++i)
cin >> b[i];
sort(a+,a+n+);
sort(b+,b+m+);
int N=;
for(int i=; i<=n; ++i) { if(a[i]==b[N])
N++;
else
cout << a[i]<<' ';
}
return ;
}
P.S祝贺詹宜瑞同学Rank1!!祝贺李博翱同学获得鼠标!!祝贺我自己Rank倒第一!!!