Encontrar el peor caso de tipo de montón

Estoy trabajando en el problema H en el concurso ACM ICPC 2004–2005 del noreste de Europa .

El problema es básicamente encontrar el peor de los casos que produce un número máximo de intercambios en el algoritmo (tamizar hacia abajo) para construir el montón.

• Entrada: el archivo de entrada contiene $n$( ).$1 \le n \le 50{,}000$
• Salida: genera la matriz que contiene números enteros diferentes de a , de modo que es un montón, y al convertirla en una matriz ordenada, el número total de intercambios en las operaciones de cribado es lo máximo posible.$n$$1$$n$

Entrada de muestra: 6
Salida correspondiente:6 5 3 2 4 1

Y los resultados básicos:

[2, 1]   
[3, 2, 1]   
[4, 3, 1, 2] 
[5, 4, 3, 2, 1] 
[6, 5, 3, 4, 1, 2]

Dado el peor de los casos para $n$, podemos construir el peor de los casos para $n+1$ de la siguiente manera: hacemos un 'ciclo de intercambio' de la siguiente manera: tomamos $n+1$, ponlo adentro $a[0]$y cambiamos $a[0]$ con el elemento máximo de sus hijos, que es $a[1]$ o $a[2]$, que nuevamente intercambiamos con el elemento máximo de sus elementos secundarios, y así sucesivamente, hasta que dejamos el $n$-elemento montón, en ese punto ponemos ese último elemento en el $n+1$-a posición.

Un ejemplo: el peor de los casos para $n=5$ es $[5, 4, 3, 2, 1]$. Intercambiamos 6 que crea el montón$[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1]$, después de lo cual terminamos con 2, que insertamos al final: $[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1, \textbf{2}]$.

El método anterior funciona por inducción: partimos del peor resultado para $n-1$ elementos y realizar una operación de cribado hacia abajo en reversa, maximizando el número de intercambios que tiene que hacer ($\lfloor\log(n)\rfloor$intercambios). No puede hacer más intercambios que este, por lo que maximiza el número de intercambios después de la primera operación de extracción mínima, después de lo cual le queda exactamente el peor de los casos para$n-1$elementos para la próxima operación extract-min. Esto implica que el número de intercambios es de hecho máximo.

Tenga en cuenta que este método proporciona resultados diferentes de los que obtuvo:

[1]
[2, 1]
[3, 2, 1]
[4, 3, 1, 2]
[5, 4, 1, 3, 2]
[6, 5, 1, 4, 2, 3]
[7, 6, 1, 5, 2, 4, 3]
[8, 7, 1, 6, 2, 4, 3, 5]
[9, 8, 1, 7, 2, 4, 3, 6, 5]
[10, 9, 1, 8, 2, 4, 3, 7, 5 ,6]

Sin embargo, ambas soluciones son correctas:

[5, 4, 1, 3, 2]
[2, 4, 1, 3| 5]
[4, 2, 1, 3| 5]
[4, 3, 1, 2| 5]
[2, 3, 1| 4, 5]
[3, 2, 1| 4, 5]

[5, 4, 3, 2, 1]
[1, 4, 3, 2| 5]
[4, 1, 3, 2| 5]
[4, 2, 3, 1| 5]
[1, 2, 3| 4, 5]
[3, 2, 1| 4, 5]

[6, 5, 1, 4, 2, 3]
[3, 5, 1, 4, 2| 6]
[5, 3, 1, 4, 2| 6]
[5, 4, 1, 3, 2| 6]
[2, 4, 1, 3| 5, 6]
[4, 2, 1, 3| 5, 6]
[4, 3, 1, 2| 5, 6]
[2, 3, 1| 4, 5, 6]
[3, 2, 1| 4, 5, 6]

[6, 5, 3, 4, 1, 2]
[2, 5, 3, 4, 1| 6]
[5, 2, 3, 4, 1| 6]
[5, 4, 3, 2, 1| 6]
[1, 4, 3, 2| 5, 6]
[4, 1, 3, 2| 5, 6]
[4, 2, 3, 1| 5, 6]
[1, 2, 3| 4, 5, 6]
[3, 2, 1| 4, 5, 6]