¿Cuál es el procedimiento para encontrar la suma contigua mínima con casi K intercambios para un conjunto entero dado de tamaño N?

Answer 1

Hola,

Gracias por A2A.

Lo mantendré simple.

Ya has descubierto la forma de encontrar la suma mínima sin intercambios, por lo que no discutiré eso.

Ahora, por los intercambios.

Llamemos a la suma mínima contigua como MS.

a1, a2, a3, a4, MS, a5, a6, a7

Esta puede ser la matriz después de haber encontrado la suma contigua mínima. (MS es la matriz contigua con suma mínima)

Ahora solo intercambiará elementos negativos. Haz esto->

• Encuentre un subconjunto (contiguo), incluyendo MS tal que (longitud del conjunto – no. De elementos negativos en ese subconjunto) <= k.
• Hacemos esto de izquierda a derecha hasta que encontremos un subconjunto con no. de elementos negativos o tamaño máximo.
• Después de esto, debe hacer dos iteraciones más. 1- De todos los elementos fuera del subconjunto encontrados en el paso anterior, encuentre los -ve y cámbielos por el elemento izquierdo o derecho de MS. Actualice la nueva MS.
• Cuando se realiza la iteración anterior para todos los elementos fuera de la matriz secundaria. Haga que todos los números -ve sean contiguos con swaps. El no de swaps no irá más allá de k, ya que mantuvimos un control al encontrar el subconjunto.

Hagámoslo con un ejemplo, el dado por u no cubrirá todos los casos.

Entonces toma esto.

-3,4, -1,9, -2, -3, -1,5, -4,0,8, -1,3,5,7

15 elementos, ahora podría encontrar la matriz de suma mínima MS [4: 6] (indexación basada en 0) = -6

Tomemos k = 3

ahora en una iteración O (n) a través de toda la matriz, encuentre una submatriz que incluya MS de manera que len (submatriz) – no. de elementos negativos <= k

Eso sería una matriz del índice- [0: 7] => -3,4, -1,9, -2, -3, -1,5

Len = 8

-ve elementos = 5, por lo tanto, la diferencia es <= k

Ahora, los elementos -ve fuera de este subconjunto son -4, -1.

Intercambíelos con el elemento izquierdo o derecho de MS, es decir, con 9 a la izquierda o 5 a la derecha.

Actualice MS a [3: 6] o [4: 7] respectivamente.

hazlo por todos hasta k intercambios utilizados o no haya más elementos -ve afuera!

Complejidad del tiempo

En)…

Peor caso – O (nlogn)

Espero que aclare

Gracias.

Answer 2

Podemos nombrarlo tipo de selección modificado. En el orden de selección recorrimos la lista y mientras recorrimos cada elemento hacemos lo siguiente.

Para cada elemento, encontraremos el elemento más pequeño de los elementos presentes en el lado derecho del elemento actual. Luego lo intercambiaremos con el elemento actual. Al hacer esto, construiremos el orden ascendente desde el principio. Estos elementos estarán al principio junto con un orden ordenado entre ellos.

La suma será agregando los dos elementos iniciales (según su elección) que contribuirán a la suma mínima. Por lo tanto, para esto solo necesitamos el máximo ‘dos’ intercambios con O (n) complejidad de tiempo.