数据结构_just

问题描述

给定两个序列 a b，序列 a 原先是一个单调递增的正数序列，但是由于某些
原因，使得序列乱序了，并且一些数丢失了（用 0 表示）。经过数据恢复后，找
到了正数序列 b ，且序列 a 中 0 的个数等于序列 b 的个数，打算使用序列 b 恢
复序列 a 。
对于序列 a 来说，我们可以交换两个位置上的非零的数，并且可以交换任意
次。序列 b 同样也可以进行任意次交换。
现在要将序列 b 填充到序列 a 中的值丢失的位置上，序列 b 中的每个数只能
填充一次，问最后构成的序列是否是单调递增的，如果是，则输出填充后的序列，
否则输出-1。

★数据输入
输入给定 N M，表示序列 a 和序列 b 的长度。第一行为序列 a ，第二行为
序列 b。题目保证除了 0 以外的数，在序列 a 和 b 中只出现一次。
数据保证:
80%的数据， N, M <= 100
100%的数据， N, M <= 100000, 0 <= a[i] <= 100000, 0 < b[i] <= 100000

★数据输出
如果最后序列 a 是单调递增的，输出该序列，否则输出-1。

输入示例	输出示例
4 2 0 11 0 15 1 12	1 11 12 15

输入示例	输出示例
4 2 0 0 11 15 1 12	-1

思路：

　　用三个数组:

　　　　用 a0[ ] 存输入的序列a

　　　　用 a[ ] 存序列a中不带0的元素

　　　　用b[ ] 存序列b

　　用归并对 a[ ] 与b[ ]排序　（由于数据<=100000的原因，用计数排序会更快O(n) ；不用快排是最坏会O(n^2)，怕OJ故意出比较坑的数据）

　　将a[ ] 与b[ ]插入a0[ ] ，检测是否可行

code

 #include <stdio.h>

 #include <stdlib.h>

 int buf[]={};

 inline int max(int a,int b)

 {

     return a>b?a:b;

 }

 void mergesort(int *p,int l,int r)

 {

     if(l>=r) return;

     if(l+==r)

     {

         if(p[l]>p[r])

         {

             p[l]^=p[r];

             p[r]^=p[l];

             p[l]^=p[r];

         }

         return;

     }

     int i,j,k;

     int m = (l+r)/;

     mergesort(p,l,m);

     mergesort(p,m+,r);

     for(i=l; i<=r; i++) buf[i]=p[i];

     for(k=l,i=l,j=m+; k<=r; k++)

     {

         if(i>m)                 p[k]=buf[j++];

         else if(j>r)            p[k]=buf[i++];

         else if(buf[i]<buf[j])    p[k]=buf[i++];

         else                    p[k]=buf[j++];

     }

 }

 int main()

 {

     int i,j,k;

     int a_len=;

     int a0_len,b_len,tmp;

     scanf("%d %d",&a0_len,&b_len);

     int *a0 = (int *)malloc(sizeof(int)*a0_len);

     int *a = (int *)malloc(sizeof(int)*a0_len);

     int *b = (int *)malloc(sizeof(int)*b_len);

     //--------------------------------------------------------

     for(i=; i<a0_len; i++)

     {

         scanf("%d",a0+i);

         if(a0[i]!=)

         {

             a[a_len++]=a0[i];

         }

     }

     for(i=; i<b_len; i++)

     {

         scanf("%d",b+i);

     }

     mergesort(a,,a_len-);

     mergesort(b,,b_len-);

     bool flag = true;

     for(i=,j=,k=; k<a0_len; k++)

     {

         if(a0[k]==)

         {

             a0[k]=b[j++];

         }

         else

         {

             a0[k]=a[i++];

         }

         if(k!= && a0[k]<a0[k-])

         {

             flag = false;

             break;

         }

     }

     if(flag)

     {

         for(i=;i<a0_len;i++)

         {

             printf("%d ",a0[i]);

         }

     }

     else

     {

         printf("-1");

     }

     printf("\n");

     //--------------------------------------------------------

     free(a);

     free(b);

     free(a0);

     return ;

 }

巴特西

数据结构_just_sort

最新文章

热门文章