Número máximo de explosiones de bombas que pueden ocurrir antes de que atrapen al ladrón

Dada una array , arr[] de M enteros, donde el i ^-ésimo elemento representa el tiempo después del cual explotará la i ^-ésima bomba después de lanzarla, y tres enteros N, X e Y que representan el número de celdas continuas adyacentes en el X -coordinar , y las posiciones iniciales de la celda de un ladrón y la policía. La tarea es encontrar el número máximo de explosiones de bombas que pueden ocurrir antes de que atrapen al ladrón si, en cada segundo, el ladrón puede lanzar una bomba o moverse hacia la izquierda o hacia la derecha de una celda existente que no visita la policía.

 Ejemplos:

Entrada: arr[] = {1, 4}, N = 7, X = 3, Y = 6
Salida: 2
Explicación: 
Una forma posible es:

1. En t = 0: El ladrón suelta la bomba con un tiempo de activación igual a 4. Mientras tanto, la policía avanza una celda hacia el ladrón. A partir de entonces, las posiciones del ladrón y del policía son 3 y 5 respectivamente.
2. En t = 1: La policía mueve una celda hacia el ladrón y el ladrón mueve una celda a su izquierda. A partir de entonces, las posiciones del ladrón y del policía son 2 y 4 respectivamente.
3. En t = 2: La policía mueve una celda hacia el ladrón y el ladrón mueve una celda a su izquierda. A partir de entonces, las posiciones del ladrón y del policía son 1 y 3 respectivamente.
4. En t = 3: La policía mueve una celda hacia el ladrón y el ladrón suelta la bomba con un tiempo de activación igual a 1. A partir de entonces, las posiciones del ladrón y la policía son 1 y 2 respectivamente.
5. En t = 4: Las bombas lanzadas en el tiempo (t = 3, y t = 0) estalla. Ahora el ladrón no puede moverse a ninguna celda y no le quedan bombas. La policía mueve una celda hacia el ladrón y finalmente lo atrapa en la celda 1.

Por lo tanto, el máximo de explosiones de bombas que ocurrieron antes de que atraparan al ladrón es 2.

Entrada: arr[] = {5, 1}, N = 7, X = 3, Y = 6
Salida: 1

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones: 

1. Si tanto la policía como el ladrón se mueven de manera óptima, cada segundo la policía se moverá hacia el ladrón. Por lo tanto, el tiempo máximo que tiene el ladrón antes de ser atrapado es la distancia entre sus posiciones.
2. Se puede observar que la mejor opción es dejar caer la bomba con más tiempo de activación primero que con menos tiempo de activación. Si se lanza primero una bomba con menos tiempo y luego se deja caer la bomba con más tiempo de activación, puede exceder el tiempo que tiene el ladrón antes de ser atrapado.

Siga los pasos a continuación para resolver el problema:

• Ordene la array arr[] en orden descendente.
• Inicialice dos variables, digamos conteo y tiempo con valor 0 para almacenar el conteo máximo de la explosión de bomba que puede ocurrir y el tiempo transcurrido.
• Encuentre la diferencia absoluta entre X e Y y guárdela en una variable, digamos maxSec .
• Iterar en el rango [0, M-1] , usando la variable i , y realizar los siguientes pasos:
  • Si la suma del elemento actual y el tiempo es menor o igual que maxSec , entonces incremente el conteo y el tiempo en 1 .
• Después del paso anterior, actualice el conteo como conteo = min(conteo, abs(XY)-1).
• Finalmente, después de completar los pasos anteriores, imprima el valor de count como respuesta.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum number
// of bomb that can be blasted before
// the thief gets caught
int findMaxBomb(int N, int M, int X, int Y, int arr[])
{
    // Sort the array arr[] in
    // descending order
    sort(arr, arr + M, greater<int>());
 
    // Stores the maxtime the thief
    // has before getting caught
    int maxSec;
 
    // If Y is less than X
    if (Y < X) {
        maxSec = N - Y;
    }
    // Otherwise
    else {
        maxSec = Y - 1;
    }
 
    // Stores the current
    // second
    int time = 1;
 
    // Stores the count of
    // bomb blasts
    int count = 0;
 
    // Traverse the array arr[]
    for (int i = 0; i < M; i++) {
 
        // If arr[i]+time is less
        // than or equal to the
        // maxSec
        if (arr[i] + time <= maxSec) {
            // Increment time and
            // count by 1
            time++;
            count++;
        }
    }
 
    // Update count
    count = min(count, abs(X - Y) - 1);
 
    // Return the value of count
    return count;
}
 
// Driver Code
int main()
{
    // Given Input
    int N = 7, X = 3, Y = 6;
    int arr[] = { 1, 4 };
    int M = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << findMaxBomb(N, M, X, Y, arr);
    return 0;
}

// Java program for the above approach
import java.util.Arrays;
import java.util.Collections;
 
public class GFG {
 
    // Function to find the maximum number
    // of bomb that can be blasted before
    // the thief gets caught
    static int findMaxBomb(int N, int M, int X, int Y,
                           Integer arr[])
    {
        // Sort the array arr[] in
        // descending order
        Arrays.sort(arr, Collections.reverseOrder());
 
        // Stores the maxtime the thief
        // has before getting caught
        int maxSec;
 
        // If Y is less than X
        if (Y < X) {
            maxSec = N - Y;
        }
        // Otherwise
        else {
            maxSec = Y - 1;
        }
 
        // Stores the current
        // second
        int time = 1;
 
        // Stores the count of
        // bomb blasts
        int count = 0;
 
        // Traverse the array arr[]
        for (int i = 0; i < M; i++) {
 
            // If arr[i]+time is less
            // than or equal to the
            // maxSec
            if (arr[i] + time <= maxSec) {
                // Increment time and
                // count by 1
                time++;
                count++;
            }
        }
 
        // Update count
        count = Math.min(count, Math.abs(X - Y) - 1);
 
        // Return the value of count
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Given Input
        int N = 7, X = 3, Y = 6;
        Integer arr[] = { 1, 4 };
        int M = arr.length;
 
        // Function Call
        System.out.println(findMaxBomb(N, M, X, Y, arr));
    }
}
 
// This code is contributed by abhinavjain194

# Python3 program for the above approach
 
# Function to find the maximum number
# of bomb that can be blasted before
# the thief gets caught
def findMaxBomb(N, M, X, Y, arr):
     
    # Sort the array arr[] in
    # descending order
    arr.sort(reverse = True)
 
    # Stores the maxtime the thief
    # has before getting caught
    maxSec = 0
 
    # If Y is less than X
    if (Y < X):
        maxSec = N - Y
 
    # Otherwise
    else:
        maxSec = Y - 1
 
    # Stores the current
    # second
    time = 1
 
    # Stores the count of
    # bomb blasts
    count = 0
 
    # Traverse the array arr[]
    for i in range(M):
         
        # If arr[i]+time is less
        # than or equal to the
        # maxSec
        if (arr[i] + time <= maxSec):
             
            # Increment time and
            # count by 1
            time += 1
            count += 1
 
    # Update count
    count = min(count, abs(X - Y) - 1)
 
    # Return the value of count
    return count
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    N = 7
    X = 3
    Y = 6
    arr = [ 1, 4 ]
    M = len(arr)
 
    # Function Call
    print(findMaxBomb(N, M, X, Y, arr))
 
# This code is contributed by ipg2016107

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the maximum number
// of bomb that can be blasted before
// the thief gets caught
static int findMaxBomb(int N, int M, int X,
                       int Y, int[] arr)
{
     
    // Sort the array arr[] in
    // descending order
    Array.Sort(arr);
 
    // Reverse array
    Array.Reverse(arr);
 
    // Stores the maxtime the thief
    // has before getting caught
    int maxSec;
 
    // If Y is less than X
    if (Y < X)
    {
        maxSec = N - Y;
    }
     
    // Otherwise
    else
    {
        maxSec = Y - 1;
    }
 
    // Stores the current
    // second
    int time = 1;
 
    // Stores the count of
    // bomb blasts
    int count = 0;
 
    // Traverse the array arr[]
    for(int i = 0; i < M; i++)
    {
         
        // If arr[i]+time is less
        // than or equal to the
        // maxSec
        if (arr[i] + time <= maxSec)
        {
             
            // Increment time and
            // count by 1
            time++;
            count++;
        }
    }
 
    // Update count
    count = Math.Min(count, Math.Abs(X - Y) - 1);
 
    // Return the value of count
    return count;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given Input
    int N = 7, X = 3, Y = 6;
    int[] arr = { 1, 4 };
    int M = arr.Length;
 
    // Function Call
    Console.WriteLine(findMaxBomb(N, M, X, Y, arr));
}
}
 
// This code is contributed by target_2

<script>
 
        // JavaScript program for the above approach
 
 
        // Function to find the maximum number
        // of bomb that can be blasted before
        // the thief gets caught
        function findMaxBomb(N, M, X, Y, arr) {
            // Sort the array arr[] in
            // descending order
            arr.sort(function (a, b) { return b - a })
 
            // Stores the maxtime the thief
            // has before getting caught
            let maxSec;
 
            // If Y is less than X
            if (Y < X) {
                maxSec = N - Y;
            }
            // Otherwise
            else {
                maxSec = Y - 1;
            }
 
            // Stores the current
            // second
            let time = 1;
 
            // Stores the count of
            // bomb blasts
            let count = 0;
 
            // Traverse the array arr[]
            for (let i = 0; i < M; i++) {
 
                // If arr[i]+time is less
                // than or equal to the
                // maxSec
                if (arr[i] + time <= maxSec) {
                    // Increment time and
                    // count by 1
                    time++;
                    count++;
                }
            }
 
            // Update count
            count = Math.min(count, Math.abs(X - Y) - 1);
 
            // Return the value of count
            return count;
        }
 
        // Driver Code
 
        // Given Input
        let N = 7, X = 3, Y = 6;
        let arr = [1, 4];
        let M = arr.length;
 
        // Function Call
        document.write(findMaxBomb(N, M, X, Y, arr));
 
    // This code is contributed by Potta Lokesh
 
</script>

2

Complejidad de tiempo: O(M*log(M)), donde M es el tamaño de la array arr[].
Espacio Auxiliar: O(1)