题意分析

本题主要围绕堆排序算法展开，要求找出一个特定的堆化数组，使得在将其转换为有序数组的过程中，向下筛选操作的交换总次数达到最大。下面从堆排序算法、问题核心以及输入输出要求等方面进行详细分析。

堆排序算法

堆排序是一种时间复杂度为 O(nlogn) 、额外空间复杂度为 O(1) 的确定性排序算法，它主要分为两个阶段：

建堆阶段（heapification）：将待排序的整数数组转换为一个堆。对于数组 a[1…n] ，若满足以下两个条件，则称其为堆： 当 2i≤n 时， a[i]>a[2i] 。 当 2i+1≤n 时， a[i]>a[2i+1] 。 可以将数组看作一棵二叉树， a[i] 的子节点为 a[2i] 和 a[2i+1] ，父节点为 a[i div 2] （ i div 2 表示 i 除以 2 向下取整）。从树的角度看，堆的性质意味着每个节点的值都大于其孩子节点的值。

排序阶段：

提取最大值（extract - max）：由于堆的性质，堆化数组中最大的元素是 a[1] 。将 a[1] 与 a[n] 交换，这样最大元素就位于已排序数组的正确位置。 向下筛选（sifting down）：交换后，数组的前 n−1 个元素可能不再满足堆的条件，需要对 a[1] 进行调整，将其与最大子节点交换，以恢复堆的性质。如果交换后新位置仍不满足堆条件，则继续交换，直到整个 a[1…n−1] 部分重新成为堆。重复此过程，直到整个数组有序。

问题核心

本题的核心是找到一个由 1 到 n 的不同数字组成的堆化数组，使得在将该数组通过堆排序转换为有序数组的过程中，向下筛选操作的交换总次数达到最大。例如，当 n=5 时，数组 (5,4,3,2,1) 在转换过程中的交换次数为 4 ，是 n=5 时的最大交换次数。

解题思路

构造一个最大堆，使得每次向下筛选时节点尽可能沿最长路径交换。具体通过层序填充最大剩余值（优先左子树），形成深度最大的完全二叉树结构。每个节点的左右子节点取当前剩余最大数，确保筛选时路径最长，交换次数最大化。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=5e4+9;
int heap[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int t=i;
        while(t>1)
        {
            heap[t]=heap[t>>1];
            t>>=1;
        }
        heap[t]=i+1;
    }
    heap[n]=1;
    for(int i=1;i<=n;i++)
    {
        if(i!=n)
        printf("%d ",heap[i]);
        else
        printf("%d\n",heap[i]);
    }

    return 0;
}