Minimiser les indices des consécutifs

Étant donné un tableau X[] de longueur impaire N(N ≥ 3) et un entier K Disposez les éléments de X[] de telle manière que la représentation binaire fusionnée de tous les éléments disons S a le nombre minimum d’indices je tel que S_je=S_je+1= 1. Ensuite, vous devez effectuer l’opération donnée K fois où vous pouvez incrémenter n’importe quel élément de 1 sur le tableau initial, la tâche est de retourner l’arrangement des éléments suivant la condition donnée pour minimiser les indices tels que
S_je=S_je+1= 1 dans la représentation binaire des nouveaux éléments d’arrangement et médiane maximisée de X[] qui peut être maximisé en utilisant l’opération donnée.

Note: S’il existe plusieurs arrangements satisfaisant les critères donnés, imprimez tout arrangement valide.

Exemples:

Saisir: N = 3, X[] = {3, 6, 5}, K = 2
Sortir: Disposition = 6 5 3
Médiane maximale = 6
Explication:

Arrangement:

Les représentations binaires de 6, 5 et 3 sont respectivement 110, 101 et 11. La chaîne S est formée en fusionnant toutes les représentations binaires : 11010111. Il possède 3 indices i (1, 6 et 7) tels que S_je=S_je+1= 1. Quels sont le nombre minimum possible de tels indices.

Médiane maximale :

Initiale X[]: {3, 6, 5}

Choisissons X[3] = 5, et incrémentez-le de 1. Puis mis à jour X[] est : {3, 6, 6}

Choisissons X[3] = 6, et incrémentez-le de 1. Puis mis à jour X[] est : {3, 67}

On peut vérifier qu’en utilisant une opération donnée sous K = 2 fois, la médiane ne peut pas être maximisée à plus de 6.

Saisir: N = 5, X[] = {5, 3, 1, 2, 3}, K = 4
Sortir: Disposition = 3 1 2 3 5
Médiane maximale = 5
Explication: Il peut être vérifié que les entrées ci-dessus généreront les sorties conformément à l’énoncé du problème.

Approche: Mettez en œuvre l’idée ci-dessous pour résoudre le problème :

Le problème est observation et Logique gourmande basé et peut être résolu en utilisant quelques observations. Les observations sont liées aux nombres impairs présents à l’intérieur de X[]. Pour maximiser la médiane d’abord Trier X[]puis incrémenter l’élément médian, Formellement X[mid] += 1 puis déplacer X[mid] à sa position triée respective. Vous pouvez suivre cette approche K fois

Des mesures ont été prises pour résoudre le problème :

Des mesures ont été prises pour l’aménagement :
- Créer une variable disons impair et l’initialiser égal à -1,
- Créer un objet StringBuilder disons qn.
- Exécuter une boucle pour traverser X[] et suivez les étapes ci-dessous dans le cadre de la boucle :
  - si (X[ i ] % 2 ! = 0 && impair == -1), alors impair = X[ i ]
  - sinon Sb.append( X[ i ] )
- if (odd != -1) then Sb.append(odd)
- Sortie StringBuilder Sb.
Des mesures ont été prises pour maximiser la médiane :
- Trier X[].
- Créer une variable disons milieu = (X.longueur – 1)/2
- Exécutez une boucle K fois et suivez les étapes ci-dessous dans le cadre de la boucle :
  - Incrément X[mid]Formellement X[mid] += 1
  - Échanger X[mid] sur son côté droit à sa position triée respective.
- Sortie X[mid].

Ci-dessous le code pour implémenter l’approche:

Java

// Java code to implement the approach
import java.io.*;
import java.lang.*;
import java.util.*;

class GFG {

    // Driver Function
    public static void main(String[] args)
        throws java.lang.Exception
    {

        // Inputs
        int N = 3;
        int K = 2;
        int X[] = { 3, 6, 5 };

        // Function call for arrangement
        System.out.print("Arrangement : ");
        Arrangement(N, X);

        // Function call for Maximum
        // Max_Median
        Max_Median(K, X);
    }

    // Method for valid arrangements
    static void Arrangement(int N, int X[])
    {
        int odd = -1;

        // StringBuilder object created
        StringBuilder sb = new StringBuilder();

        // Loop for traversing over X[]
        for (int i = 0; i < N; i++) {
            if (X[i] % 2 != 0 && odd == -1) {
                odd = X[i];
            }
            else {
                sb.append(X[i]);
                sb.append(" ");
            }
        }
        if (odd != -1) {
            sb.append(odd);
        }

        // Printing arrangement
        System.out.println(" " + sb);
    }

    // Method for maximizing median
    static void Max_Median(int K, int X[])
    {

        // Sorting X[] using in-built sort
        // function
        Arrays.sort(X);

        // Calculating mid-index
        int mid = (X.length - 1) / 2;

        // Loop for K number of times
        for (int j = 1; j <= K; j++) {

            // Incrementing mid
            X[mid] += 1;

            // Temporary variable to hold
            // mid index value
            int i = mid;

            // Loop for sorting X[] after
            // incrementing X[mid] element
            // Formally, It swaps mid element
            // until it is greater than its
            // right adjacent element for
            // placing incremented X[mid]
            // at its sorting position
            while (X[i] > X[i + 1] && i <= X.length - 2) {
                int temp = X[i];
                X[i] = X[i + 1];
                X[i + 1] = temp;

                if (i < X.length - 2)
                    i++;
            }
        }

        // Printing Maximized median
        System.out.println("Maximum Median : " + X[mid]);
    }
}

Sortir

Arrangement :  6 5 3
Maximum Median : 6

Complexité temporelle : O(K * N), pour la disposition des nombres, O(N * Log(N)), pour trouver la médiane maximale
Espace Auxiliaire : O(1)