（TOJ1435）{A} + {B}

描述

给你两个集合，要求{A} + {B}. 注:同一个集合中不会有两个相同的元素.

输入

每组输入数据分为三行,第一行有两个数字n,m(0<n,m<=10000),分别表示集合A和集合B的元素个数.后两行分别表示集合A和集合B.每个元素为不超出int范围的整数,每个元素之间有一个空格隔开

输出

针对每组数据输出一行数据,表示合并后的集合,要求从小到大输出,每个元素之间有一个空格隔开

样例输入

样例输出

1 2 3
1 2

AC code1：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<ctype.h>
 4 #include<math.h>
 5 
 6 int a[10001],b[10001];
 7 
 8 int split(int a[],int low,int high)
 9 {
10    int part_element=a[low];
11    for(;;){
12    while(low<high&&part_element<=a[high])
13      high--;
14    if(low>=high) break;
15    a[low++]=a[high];
16  
17    while(low<high&&a[low]<=part_element)
18      low++;
19    if(low>=high) break;
20    a[high--]=a[low];
21    }
22    a[high]=part_element;
23    return high;
24 }
25 void quicksort(int a[],int low,int high)
26 {
27    int middle;
28    if(low>=high)return;
29    middle=split(a,low,high);
30    quicksort(a,low,middle-1);
31    quicksort(a,middle+1,high);
32  }
33 int deal(int c[], int n, int d[], int m)
34 {
35     int L,i,j,flag=0;
36     i=j=0;
37     while(i<n && j<m){
38         if(c[i]<d[j]){
39             if(flag)  printf(" ");
40             printf("%d",c[i]);
41             while(c[i+1]==c[i] && i+1<n) i++;
42             i++;flag=1;
43         }else if(c[i]==d[j]){
44             if(flag) printf(" ");
45             printf("%d",c[i]);
46             while(c[i+1]==c[i] && i+1<n) i++;
47             while(d[j+1]==d[j] && j+1<m) j++;
48             i++; j++; flag=1;
49         }else{
50             if(flag) printf(" ");
51             printf("%d",d[j]);
52             while(d[j+1]==d[j] && j+1<m) j++;
53             j++; flag=1;
54         }
55     }
56     if(i==n){
57         while(j<m)  
58         {
59            printf(" %d",d[j]);
60            while(d[j]==d[j+1]) j++;
61            j++;
62        }
63     }else{
64         while(i<n)
65         {
66           printf(" %d",c[i]);
67             while(c[i]==c[i+1]) i++;
68           i++;
69         }
70      }
71     printf("\n");
72 }
73 
74 void solve()
75 {
76     int i,j,n,m;
77     while(scanf("%d %d",&n,&m)!=EOF){
78     for(i=0; i<n; i++){
79         scanf("%d",&a[i]);
80     }
81     for(i=0; i<m; i++){
82         scanf("%d",&b[i]);
83     }
84     quicksort(a,0,n-1);
85     quicksort(b,0,m-1);
86     deal(a,n,b,m);
87     }
88 }
89 
90 int main()
91 {
92     solve();
93     return 0;
94 }

AC code2：

    
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>

int a[20001];

int split(int a[],int low,int high)
{
   int part_element=a[low];
   for(;;){
   while(low<high&&part_element<=a[high])
     high--;
   if(low>=high) break;
   a[low++]=a[high];
   while(low<high&&a[low]<=part_element)
     low++;
   if(low>=high) break;
   a[high--]=a[low];
   }
   a[high]=part_element;
   return high;
}

void quicksort(int a[],int low,int high)
{
   int middle;
   if(low>=high)return;
   middle=split(a,low,high);
   quicksort(a,low,middle-1);
   quicksort(a,middle+1,high);
}

void deal(int a[], int n)
{
    int i;
    printf("%d",a[0]);
    for(i=1; i<n; i++){
        if(a[i]!=a[i-1])
          printf(" %d",a[i]);
    }
    printf("\n");
} 

void solve()
{
    int i,j,n,m;
    while(scanf("%d %d",&n,&m)!=EOF){
    for(i=0; i<n+m; i++){
        scanf("%d",&a[i]);
    }
    quicksort(a,0,n+m-1);
    deal(a,n+m);
    }
}

int main()
{
    solve();
    return 0;
}

C++ code:

 1 #include<iostream>
 2 #include<vector>
 3 #include<iterator>
 4 #include <utility>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8  int main()
 9  {
10      int m,n,i,t;
11      while(cin>>n>>m)
12      {
13         vector<int>v(m+n);
14         vector<int>::iterator it;
15         for(it=v.begin(); it!=v.end(); ++it)
16         {
17             cin>>*it;
18         }
19         sort(v.begin(),v.end(),less<int>());
20         v.erase(unique(v.begin(),v.end()),v.end());
21         for(it=v.begin(); it!=v.end(); ++it)
22         {
23            if(it>v.begin())
24               cout<<" ";
25            cout<<*it;
26         }
27         cout<<endl;
28      }
29     return 0;
30  }