ZZULIOJ 1124: 两个有序数组合并

1124: 两个有序数组合并

时间限制: 1 Sec  内存限制: 128 MB

题目描述

已知数组a中有m个按升序序排列的元素，数组b中有n个降序排列的元素，编程将a与b中的所有元素按降序存入数组c中。

输入

输入有两行，第一行首先是一个正整数m，然后是m个整数；第二行首先是一个正整数n，然后是n个整数，m, n均小于等于1000000。

输出

输出合并后的m+n个整数，数据之间用空格隔开。输出占一行。

样例输入 Copy

4 1 2 5 7
3 6 4 2

样例输出 Copy

 7 6 5 4 2 2 1

#include <stdio.h>
#include <stdlib.h>
int a[1000000];
int b[1000000];
int c[2000000];
void merge(int*a,int m,int*b,int n);
void print(int *c,int cnt);
int cmp(const void*p1,const void*p2);
//整体思路，存放在一个新数组c中
int main()
{
    int m,n;
    int i,j;
    scanf("%d",&m);
    for(i=0;i<m;i++)
        scanf("%d",&a[i]);
    scanf("%d",&n);
    for(j=0;j<n;j++)
        scanf("%d",&b[j]);
    merge(a,m,b,n);
    qsort(c,m+n,sizeof(c[0]),cmp);
    print(c,m+n);
    return 0;
}

void merge(int*a,int m,int*b,int n)
{
    int i=0,j=0,k=0;
    while(i<m&&j<n)
    {
        if(a[i]>b[j])    c[k++]=a[i++];
        else    c[k++]=b[j++];
    }
    while(i<m)
    {
        c[k++]=a[i++];
    }
    while(j<n)
    {
        c[k++]=b[j++];
    }
}
void print(int *c,int cnt)
{
    int i;
    for(i=0;i<cnt;i++)
    {
        printf("%d ",c[i]);
    }
}
int cmp(const void*p1,const void*p2)
{
    return *(int*)p2-*(int*)p1;
}