1089 Insert or Merge (25 分)

非原创，参考：https://blog.csdn.net/richenyunqi/article/details/81150510
 1 #pragma warning(disable:4996)
 2 #define _CRT_SECURE_NO_WARNINGS
 3 
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <vector>
 8 #include <map>
 9 #include <set>
10 #include <unordered_set>
11 #include <unordered_map>
12 #include <queue>
13 #include <cmath>
14 #include <string>
15 #include <cstring>
16 #define INFINITE 2000000000
17 using namespace std;
18 
19 
20 int main() {
21     int n;
22     cin >> n;
23     int v1[110], v2[110], A[110];
24     for (int i = 0; i < n; ++i) cin >> v1[i];
25     for (int i = 0; i < n; ++i) cin >> v2[i];
26     int flag = 0;
27     memcpy(A, v1, sizeof(int) * n);
28     for (int i = 1; i < n; ++i) {
29         sort(A, A + i + 1);
30         if(equal(A, A+n, v2)){
31             sort(A, A + i + 2);
32             flag = 1;
33             cout << "Insertion Sort" << endl;
34             break;
35         }
36     }
37     if (!flag) {
38         cout << "Merge Sort" << endl;
39         memcpy(A, v1, sizeof(int)*n);//每step个元素排序
40         for (int step = 2; step < n; step *= 2) {
41             for (int i = 0; i < n; i+=step) {
42                 sort(A + i, A + min(i + step, n));
43             }
44             if (equal(A, A + n, v2)) {
45                 for (int i = 0; i < n; i+=step*2) 
46                     sort(A + i, A + min(i + step*2, n));
47                 break;
48             }
49         }
50     }
51     for (int i = 0; i < n; ++i) {
52         if (i != 0) cout << " ";
53         cout << A[i];
54     }
55     return 0;
56 }