数据结构_just

数据结构_just_sort

问题描述

给定两个序列 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

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 int buf[100001]={0};
 5 
 6 inline int max(int a,int b)
 7 {
 8     return a>b?a:b;
 9 }
10 
11 void mergesort(int *p,int l,int r)
12 {
13     if(l>=r) return;
14     if(l+1==r)
15     {
16         if(p[l]>p[r])
17         {
18             p[l]^=p[r];
19             p[r]^=p[l];
20             p[l]^=p[r];
21         }
22         return;
23     }
24     int i,j,k;
25     int m = (l+r)/2;
26     mergesort(p,l,m);
27     mergesort(p,m+1,r);
28     for(i=l; i<=r; i++) buf[i]=p[i];
29     for(k=l,i=l,j=m+1; k<=r; k++)
30     {
31         if(i>m)                 p[k]=buf[j++];
32         else if(j>r)            p[k]=buf[i++];
33         else if(buf[i]<buf[j])    p[k]=buf[i++];
34         else                    p[k]=buf[j++];
35     }
36 }
37 
38 int main()
39 { 
40     int i,j,k;
41     int a_len=0;
42     int a0_len,b_len,tmp;
43     scanf("%d %d",&a0_len,&b_len);
44     int *a0 = (int *)malloc(sizeof(int)*a0_len);
45     int *a = (int *)malloc(sizeof(int)*a0_len);
46     int *b = (int *)malloc(sizeof(int)*b_len);
47     //--------------------------------------------------------
48     for(i=0; i<a0_len; i++)
49     {
50         scanf("%d",a0+i);
51         if(a0[i]!=0)
52         {
53             a[a_len++]=a0[i];
54         }
55     }
56     for(i=0; i<b_len; i++)
57     {
58         scanf("%d",b+i);
59     }
60     mergesort(a,0,a_len-1);
61     mergesort(b,0,b_len-1);
62     
63     bool flag = true;
64     for(i=0,j=0,k=0; k<a0_len; k++)
65     {
66         if(a0[k]==0)
67         {
68             a0[k]=b[j++];
69         }
70         else
71         {
72             a0[k]=a[i++];
73         }
74         if(k!=0 && a0[k]<a0[k-1])
75         {
76             flag = false;
77             break;
78         }
79     }
80         
81 
82     if(flag)
83     {
84         for(i=0;i<a0_len;i++)
85         {
86             printf("%d ",a0[i]);
87         }
88     }
89     else
90     {
91         printf("-1");
92     }
93     printf("
");
94     //--------------------------------------------------------
95     free(a);
96     free(b);
97     free(a0);
98     return 0;
99 }