Saltos mínimos necesarios para que un grupo de personas se siente juntas

Dada una string S de longitud N que consta de ‘x’ y ‘.’ . La string dada representa una fila de asientos donde ‘x’ y ‘.’ representan asientos ocupados y desocupados respectivamente. La tarea es minimizar el número total de saltos o brincos para que todos los ocupantes se sienten juntos, es decir, uno al lado del otro, sin que haya ningún asiento libre entre ellos. 

Nota: Dado que la cuenta de saltos puede ser muy grande, imprima la respuesta módulo 10 ⁹ + 7 .

Ejemplos:

Entrada: S = “. . . . X . . xx . . X . .”
Resultado: 5
Explicación: A continuación se muestran los cambios necesarios de ocupantes:
Paso 1: Haga que la persona en el 5 ^to asiento salte 2 lugares al 7 ^to asiento.
Paso 2: Haz que la persona en el asiento 13 ^salte 3 lugares hasta el asiento ¹⁰ .
Por lo tanto, número total de saltos requeridos = 2 + 3 = 5.

Entrada: S = “xxx. . . . . . . . xxxxxx”
Salida: ²⁴ Explicación
: Mover a los ocupantes de la posición 1 ^, 2 ^y 3 ^a las posiciones 9 ^, 10 ^y 11 respectivamente. Por lo tanto, el número total de saltos necesarios = (11 – 3) + (10 – 2) + (9 – 3) = 24.

Enfoque: la idea es utilizar un enfoque codicioso para resolver este problema. Observe que siempre es óptimo desplazar los elementos hacia el elemento mediano entre las personas o la persona central entre todas las personas presentes. El número de saltos siempre será mínimo cuando desplazamos puntos a la mediana. A continuación se muestran los pasos:

• Inicialice una posición de vector para almacenar los índices de las personas presentes.
• Encuentre la mediana del vector position[] . Ahora se hará que todas las demás personas se sienten alrededor de esta persona, ya que esto dará el número mínimo de saltos necesarios para realizar.
• Inicialice una variable ans que almacene los saltos mínimos requeridos.
• Ahora, recorra la posición del vector [] y para cada índice encuentro el elemento mediano y actualizo como :

ans= ans+ abs(posición[i] – elementomediano)

• Después de los pasos anteriores, imprima el valor de ans como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
long long int MOD = 1e9 + 7;
 
// Function to find the minimum jumps
// required to make the whole group
// sit adjacently
int minJumps(string seats)
{
    // Store the indexes
    vector<int> position;
 
    // Stores the count of occupants
    int count = 0;
 
    // Length of the string
    int len = seats.length();
 
    // Traverse the seats
    for (int i = 0; i < len; i++) {
 
        // If current place is occupied
        if (seats[i] == 'x') {
 
            // Push the current position
            // in the vector
            position.push_back(i - count);
            count++;
        }
    }
 
    // Base Case:
    if (count == len || count == 0)
        return 0;
 
    // The index of the median element
    int med_index = (count - 1) / 2;
 
    // The value of the median element
    int med_val = position[med_index];
 
    int ans = 0;
 
    // Traverse the position[]
    for (int i = 0;
         i < position.size(); i++) {
 
        // Update the ans
        ans = (ans % MOD
               + abs(position[i]
                     - med_val)
                     % MOD)
              % MOD;
    }
 
    // Return the final count
    return ans % MOD;
}
 
// Driver Code
int main()
{
    // Given arrange of seats
    string S = "....x..xx...x..";
 
    // Function Call
    cout << minJumps(S);
 
    return 0;
}

// Java program for the
// above approach
import java.util.*;
class GFG{
 
static int MOD = (int)1e9 + 7;
 
// Function to find the minimum
// jumps required to make the
// whole group sit adjacently
static int minJumps(String seats)
{
  // Store the indexes
  Vector<Integer> position =
                  new Vector<>();
 
  // Stores the count of
  // occupants
  int count = 0;
 
  // Length of the String
  int len = seats.length();
 
  // Traverse the seats
  for (int i = 0; i < len; i++)
  {
    // If current place is occupied
    if (seats.charAt(i) == 'x')
    {
      // Push the current position
      // in the vector
      position.add(i - count);
      count++;
    }
  }
 
  // Base Case:
  if (count == len ||
      count == 0)
    return 0;
 
  // The index of the median
  // element
  int med_index = (count - 1) / 2;
 
  // The value of the median
  // element
  int med_val = position.get(med_index);
 
  int ans = 0;
 
  // Traverse the position[]
  for (int i = 0;
           i < position.size(); i++)
  {
    // Update the ans
    ans = (ans % MOD +
           Math.abs(position.get(i) -
                    med_val) % MOD) % MOD;
  }
 
  // Return the final count
  return ans % MOD;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given arrange of seats
  String S = "....x..xx...x..";
 
  // Function Call
  System.out.print(minJumps(S));
}
}
 
// This code is contributed by gauravrajput1

# Python3 program for the above approach
MOD = 10**9 + 7
 
# Function to find the minimum jumps
# required to make the whole group
# sit adjacently
def minJumps(seats):
     
    # Store the indexes
    position = []
 
    # Stores the count of occupants
    count = 0
 
    # Length of the string
    lenn = len(seats)
 
    # Traverse the seats
    for i in range(lenn):
 
        # If current place is occupied
        if (seats[i] == 'x'):
 
            # Push the current position
            # in the vector
            position.append(i - count)
            count += 1
 
    # Base Case:
    if (count == lenn or count == 0):
        return 0
 
    # The index of the median element
    med_index = (count - 1) // 2
 
    # The value of the median element
    med_val = position[med_index]
 
    ans = 0
 
    # Traverse the position[]
    for i in range(len(position)):
         
        # Update the ans
        ans = (ans % MOD +
               abs(position[i] - med_val)
               % MOD) % MOD
 
    # Return the final count
    return ans % MOD
 
# Driver Code
if __name__ == '__main__':
     
    # Given arrange of seats
    S = "....x..xx...x.."
 
    # Function Call
    print(minJumps(S))
 
# This code is contributed by mohit kumar 29

// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
 
static int MOD = (int)1e9 + 7;
 
// Function to find the minimum
// jumps required to make the
// whole group sit adjacently
static int minJumps(String seats)
{
  // Store the indexes
  List<int> position =
       new List<int>();
 
  // Stores the count of
  // occupants
  int count = 0;
 
  // Length of the String
  int len = seats.Length;
 
  // Traverse the seats
  for (int i = 0; i < len; i++)
  {
    // If current place is
    // occupied
    if (seats[i] == 'x')
    {
      // Push the current
      // position in the
      // vector
      position.Add(i - count);
      count++;
    }
  }
 
  // Base Case:
  if (count == len ||
      count == 0)
    return 0;
 
  // The index of the median
  // element
  int med_index = (count - 1) / 2;
 
  // The value of the median
  // element
  int med_val = position[med_index];
 
  int ans = 0;
 
  // Traverse the position[]
  for (int i = 0;
           i < position.Count; i++)
  {
    // Update the ans
    ans = (ans % MOD +
           Math.Abs(position[i] -
           med_val) % MOD) % MOD;
  }
 
  // Return the readonly
  // count
  return ans % MOD;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given arrange of seats
  String S = "....x..xx...x..";
 
  // Function Call
  Console.Write(minJumps(S));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// Javascript program for the above approach
let MOD = 1e9 + 7;
 
// Function to find the minimum jumps
// required to make the whole group
// sit adjacently
function minJumps(seats)
{
    // Store the indexes
    let position = [];
     
    // Stores the count of occupants
    let count = 0;
     
    // Length of the string
    let len = seats.length;
     
    // Traverse the seats
    for(let i = 0; i < len; i++)
    {
         
        // If current place is occupied
        if (seats[i] == 'x')
        {
             
            // Push the current position
            // in the vector
            position.push(i - count);
            count++;
        }
    }
     
    // Base Case:
    if (count == len || count == 0)
        return 0;
     
    // The index of the median element
    let med_index = parseInt((count - 1) / 2, 10);
     
    // The value of the median element
    let med_val = position[med_index];
     
    let ans = 0;
     
    // Traverse the position[]
    for(let i = 0; i < position.length; i++)
    {
     
        // Update the ans
        ans = (ans % MOD + Math.abs(position[i] -
          med_val) % MOD) % MOD;
    }
     
    // Return the final count
    return ans % MOD;
}
 
// Driver code
 
// Given arrange of seats
let S = "....x..xx...x..";
 
// Function Call
document.write(minJumps(S));
   
// This code is contributed by suresh07
 
</script>

5

Complejidad temporal: O(N)
Espacio auxiliar: O(N)