[PAT-B] 1098 Insertion or Heap Sort

cpcs

1098 Insertion or Heap Sort

判断是插入排序还是堆排序的中间一步，和1089很像，其实只要把两种排序都实现了就好了…… 暴力做

1. #include <cstdio>
   
2. #include <cstring>
   
3. #include <string>
   
4. #include <algorithm>
   
5. 
   
6. using namespace std;
   
7. 
   
8. int a[102], b[102], c[102];
   
9. 
   
10. void print(int *a, int n) {
    
11.         for (int i = 0; i < n; ++i) {
    
12.                 if (i) {
    
13.                         putchar(' ');
    
14.                 }
    
15.                 printf("%d", a【i】);
    
16.         }
    
17.         puts("");
    
18. }
    
19. 
    
20. bool same(int *a,int *b, int n) {
    
21.     for (int i = 0; i < n; ++i) {
    
22.         if (a【i】 != b【i】) {
    
23.             return false;
    
24.         }
    
25.     }
    
26.     return true;
    
27. }
    
28. 
    
29. void insertion(int *a, int i) {
    
30.         int temp = a【i】;
    
31.         for (--i; (i >= 0) && (a【i】 > temp); --i) {
    
32.                 a[i + 1] = a【i】;
    
33.         }
    
34.         a[i + 1] = temp;
    
35. }
    
36.        
    
37.        
    
38.        
    
39. bool make1(int n) {
    
40.     for (int i = 1; i < n; ++i) {
    
41.         insertion(c, i);
    
42.         if (same(c, b, n)) {
    
43.             puts("Insertion Sort");
    
44.             insertion(c, i + 1);
    
45.             print(c, n);
    
46.             return true;
    
47.         }
    
48.         
    
49.     }
    
50.     return false;
    
51.    
    
52. }
    
53. 
    
54. void down(int *a, int i, int n) {
    
55.         for (;;) {
    
56.                 int left = (i << 1) | 1;
    
57.                 if (left >= n) {
    
58.                         break;
    
59.                 }
    
60.                 int right = left + 1;
    
61.                 int x = ((right < n) && (a[right] > a[left]))?right:left;
    
62.                 if (a【i】 > a[x]) {
    
63.                         break;
    
64.                 }
    
65.                 swap(a[x], a【i】);
    
66.                 i = x;
    
67.         }
    
68. }
    
69. 
    
70. void deleteMax(int *a,int &n) {
    
71.         swap(a[0], a[--n]);
    
72.         down(a, 0, n);
    
73. }
    
74. 
    
75. void make2(int n) {
    
76.        
    
77.         puts("Heap Sort");
    
78.         for (int i = (n >> 1) - 1; i >= 0; --i) {
    
79.                 down(a, i, n);
    
80.         }
    
81.         int m = n;
    
82.         while (!same(a, b, n)) {
    
83.                 deleteMax(a, m);
    
84.         }
    
85.         deleteMax(a, m);
    
86.         print(a, n);
    
87.                
    
88. }
    
89.        
    
90.                
    
91.                
    
92. 
    
93. int main() {
    
94. int n;
    
95.         scanf("%d", &n);
    
96.         for (int i = 0; i < n; ++i) {
    
97.                 scanf("%d", a + i);
    
98.         }
    
99.         memcpy(c, a, sizeof(int) * n);
    
100.         for (int i = 0; i < n; ++i) {
     
101.                 scanf("%d", b + i);
     
102.         }
     
103.         if (!make1(n)) {
     
104.                 make2(n);
     
105.         }
     
106.         return 0;
     
107. }
     

复制代码