题目

https://pintia.cn/problem-sets/994805342720868352/problems/994805368847187968

题意

首先，不了解堆排序流程的同学可以看看我的第二篇参考文章（插入排序较为简单，不会的同学自行学习）

题目给出两个序列a、b，a为最初序列，b为排序过的序列，问排序方式是插入排序还是堆排序，并输出下一步的排序结果

代码思路

代码思路详见参考文章第一篇

需要说明的是，low参数的使用我放在了对i的赋初值上，这样至少用到了low；至于从小到大还是从大到小，我建议大家看一下参考文章第二篇的图文讲解，结合那个讲解相信你自己就能真正理解了

AC代码

#include<bits/stdc++.h>
using namespace std;
//堆排序最开始要先构建大顶堆，但因为题目中至少已经排序了以一次，说明题目已经完成的大顶堆的准备并开始排序了
//所以我们只需要完成后面的步骤就好
void downAdjust(vector<int> &b,int low,int high)
{
	int i=low,j=low*2;
	while(j<=high)
	{
		if(j+1<=high&&b[j]<b[j+1]) j++;//根节点要与左右孩子的最大值相比，以保证得到大顶堆 
		if(b[i]>b[j]) return;//注意，这里不写=是因为堆排序不稳定，相等数字的相对位置会发生变化
		swap(b[i],b[j]);
		i=j,j=i*2;
	}	
} 
int main()
{
	int n,p=2;//序列下标从1开始，要从第二个数字开始和前一个数字比，所以p=2
	scanf("%d",&n);
	vector<int> a(n+1),b(n+1);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]); 
	while(p<=n&&b[p-1]<=b[p]) p++;//这里的 a[p-1]<=a[p]之所以有等于号是因为，插入排序是稳定的，相同数字的相对位置不变 
	int index=p;//index的位置是第一个不满足从小到大排序的数字，也就是下一次插入排序的右边界
	while(p<=n&&a[p]==b[p]) p++;
	//插入排序从index开始的数字位置都是不变的（因为没轮到它们排序），否则就是堆排序了 
	if(p==n+1)
	{
		printf("Insertion Sort\n");
		sort(b.begin(),b.begin()+index+1);
	}
	else
	{
		printf("Heap Sort\n");
		p=n;
		while(p>2&&b[p]>b[1]) p--; 
		swap(b[1],b[p]);
		downAdjust(b,1,p-1);
	}
	for(int i=1;i<=n;i++)
	{
		if(i!=1) printf(" ");
		printf("%d",b[i]);
	}
}