题目大意： 给定两个集合A、B，集合内的任一元素x满足1 ≤ x ≤10^9 ，并且每个集合的元素个数不大于10^5个。我们希望求出A、B之间的关系。只需确定在B 中但是不在 A 中的元素的个数即可。
哈希(hash): 未完成。
排序+枚举： 1.分别从小到大排序。 2.然后For一波找出他们最大的公共元素个数。 3.按题目要求输出。 时间复杂度:O(2(N+M))
const maxn=100000;var t,a,b:array[1..maxn] of longint; p,i,n,m,j:longint;PRocedure qsort(l,r:longint); var i,j,key,temp:longint; begin if l>=r then exit; i:=l;j:=r; key:=a[(l+r) div 2]; repeat while (a[i]<key) do inc(i); while (a[j]>key) do dec(j); if i<=j then begin temp:=a[i];a[i]:=a[j];a[j]:=temp; inc(i); dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end;begin read(n); for i:=1 to n do read(a[i]); read(m); for i:=1 to m do read(b[i]); qsort(1,n); t:=a; a:=b; b:=t; qsort(1,m); t:=a; a:=b; b:=t; i:=1; j:=1; while (i<=n) and (j<=m) do begin if a[i]=b[j] then begin inc(p); inc(i); inc(j); continue; end else if a[i]<b[j] then inc(i) else inc(j); end; if (n=m)and(p=n) then writeln('A equals B') else if (n<m)and(p=n) then writeln('A is a proper subset of B') else if (n>m)and(p=m) then writeln('B is a proper subset of A') else if p=0 then writeln('A and B are disjoint') else writeln('I''m confused!');end.新闻热点
疑难解答
