题目大意
给定原始序列和由某排序算法产生的中间序列，请你判断该算法是插入算法还是归并算法。首先在第1行中输出“Insertion Sort”表示插入排序、或“Merge Sort”表示归并排序；然后在第2行中输出用该排序算法再迭代一轮的结果序列。
思路
插入排序排到一半的序列满足前半部分有序，后半部分和未排序时一样。根据这个特点，先循环找到第一个不按顺序的结点（下标k）,然后循环看是否与原序列一样。若i循环到了最后一个结点（i==n），则表明时插入排序，否则是归并排序。 若是插入排序，则下一步是[0, k]有序，[k+1,n-1]和和原序列一样，则调用sort将序列的[0, k+1)排序即可。 若是归并排序，则从头开始，模拟归并排序的过程，以k = 2，4，8...为组排序，直找到和中间序列一致，再归并一次即为输出的结果。i从0到n/k，每次一段段得sort(a + i * k, a + (i + 1) * k);最后别忘记还有最后剩余部分的sort(a + (n / k) * k, a + n);
坑
判断时别忘了part[i-1]和part[i]相等的情况！错了两百次了都！！！
AC代码
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>in, part;
int main() {
int n, i, j;
scanf("%d", &n);
in.resize(n); part.resize(n);
for (i = 0;i < n;i++)scanf("%d", &in[i]);
for (i = 0;i < n;i++)scanf("%d", &part[i]);
i = 1;
while (i < n && part[i - 1] <= part[i])i++;//这里part[i-1]等于part[i]时也要继续循环！！！！！！
int k = i;
while (i < n && in[i] == part[i])i++;
if (i == n) {
printf("Insertion Sort\n");
sort(part.begin(), part.begin() + k + 1);
printf("%d", part[0]);
for (j = 1;j < n;j++)printf(" %d", part[j]);
}
else {
printf("Merge Sort\n");
vector<int>ans = in;
int u = 2;
while (ans != part) {
for (j = 0;j < n / u;j++)
sort(ans.begin() + j * u, ans.begin() + (j + 1) * u);
sort(ans.begin() + j * u, ans.end());
//n/u可能除不尽，因此最后也要把剩下的那一组排序
u = u * 2;
}
for (j = 0;j < n / u;j++)
sort(ans.begin() + j * u, ans.begin() + (j + 1) * u);
sort(ans.begin() + j * u, ans.end());
printf("%d", ans[0]);
for (j = 1;j < n;j++)printf(" %d", ans[j]);
}
return 0;
}
