Consultas para encontrar los intercambios mínimos necesarios para ordenar una array determinada con actualizaciones

Posted on by Rudeus Greyrat

Dada una array ordenada arr[] de tamaño N y una array Q[][] que tiene consultas en forma de {x, y} . En cada consulta {x, y} , actualice la array dada incrementando el valor arr[x] por y . La tarea es encontrar el número mínimo de intercambios necesarios para ordenar la array obtenida después de realizar cada consulta en la array dada individualmente.

Ejemplos:

Entrada: arr[] = {2, 3, 4, 5, 6}, Q[][] = {{2, 8}, {3, 1}}
Salida: 2 0
Explicación:
A continuación se muestra el número de intercambios necesarios para cada consulta:
Consulta 1: Incremente arr[2] en 8. Por lo tanto, arr[] = {2, 3, 12, 5, 6}.
Para ordenar esta array, desplace 12 a la derecha 2 posiciones.
Ahora arr[] = {2, 3, 5, 6, 12}. Por lo tanto, requiere 2 intercambios. 
Consulta 2: Incremente arr[3] en 1. Por lo tanto, arr[] = {2, 3, 4, 6, 6}.
La array todavía está ordenada. Por lo tanto, requiere 0 intercambios. 

Entrada: arr[] = {2, 3, 4, 5, 6}, Q[][] = {{0, -1}, {4, -11}};
Salida: 0 4
Explicación:
A continuación se muestra el número de intercambios necesarios para cada consulta:
Consulta 1: Incremente arr[0] en -1. Por lo tanto, arr[] = {1, 3, 4, 5, 6}.
La array todavía está ordenada. Por lo tanto, requiere 0 intercambios.
Consulta 2: Incrementar arr[4] en -11. Por lo tanto, arr[] = {2, 3, 4, 5, -5}.
Para ordenar esta array, desplace -5 a la izquierda 4 posiciones.
Ahora arr[] = {-5, 2, 3, 4, 5}. Por lo tanto, requiere 4 intercambios. 

Enfoque ingenuo: el enfoque más simple es actualizar la array dada incrementando el valor arr[x] por y para cada consulta {x, y} . Después de eso, recorra la array actualizada e intercambie arr[x] a la derecha mientras arr[x] es mayor que arr[x+1] , incrementando x cada vez y luego intercambie arr[x] a la izquierda mientras arr[x] es menor que arr[x-1] , decrementando x cada vez. Imprime la diferencia absoluta entre el valor inicial y final de x .

Complejidad de tiempo: O(Q*N 2 ) donde N es la longitud de la array dada y Q es el número total de consultas.
Espacio Auxiliar: O(N)

Enfoque eficiente: la idea es utilizar la búsqueda binaria para encontrar el número mínimo de intercambios necesarios para ordenar la array dada después de cada consulta. Siga los pasos a continuación para resolver el problema:

  1. Para cada consulta {x, y} , almacene el valor arr[x]+y en una variable newElement .
  2. Con la búsqueda binaria , encuentre el índice del valor presente en la array dada que sea menor o igual que el valor newElement .
  3. Si no se puede encontrar dicho valor, imprima x , de lo contrario, deje que ese valor esté en el índice j .
  4. Imprime la diferencia absoluta entre el índice i y el índice j .

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the position of
// the given value using binary search
int computePos(int arr[], int n,
               int value)
{
    // Return 0 if every value is
    // greater than the given value
    if (value < arr[0])
        return 0;
 
    // Return N-1 if every value is
    // smaller than the given value
    if (value > arr[n - 1])
        return n - 1;
 
    // Perform Binary Search
    int start = 0;
    int end = n - 1;
 
    // Iterate till start < end
    while (start < end) {
 
        // Find the mid
        int mid = (start + end + 1) / 2;
 
        // Update start and end
        if (arr[mid] >= value)
            end = mid - 1;
        else
            start = mid;
    }
 
    // Return the position of
    // the given value
    return start;
}
 
// Function to return the number of
// make the array sorted
void countShift(int arr[], int n,
                vector<vector<int> >& queries)
{
    for (auto q : queries) {
 
        // Index x to update
        int index = q[0];
 
        // Increment value by y
        int update = q[1];
 
        // Set newElement equals
        // to x + y
        int newElement = arr[index]
                         + update;
 
        // Compute the new index
        int newIndex = computePos(
            arr, n, newElement);
 
        // Print the minimum number
        // of swaps
        cout << abs(newIndex - index)
             << " ";
    }
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 2, 3, 4, 5, 6 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given Queries
    vector<vector<int> > queries
        = { { 0, -1 }, { 4, -11 } };
 
    // Function Call
    countShift(arr, N, queries);
 
    return 0;
}

Java

// Java program for the
// above approach
import java.util.*;
class GFG{
 
// Function to return the position of
// the given value using binary search
static int computePos(int arr[],
                      int n, int value)
{
  // Return 0 if every value is
  // greater than the given value
  if (value < arr[0])
    return 0;
 
  // Return N-1 if every value is
  // smaller than the given value
  if (value > arr[n - 1])
    return n - 1;
 
  // Perform Binary Search
  int start = 0;
  int end = n - 1;
 
  // Iterate till start < end
  while (start < end)
  {
    // Find the mid
    int mid = (start +
               end + 1) / 2;
 
    // Update start and end
    if (arr[mid] >= value)
      end = mid - 1;
    else
      start = mid;
  }
 
  // Return the position of
  // the given value
  return start;
}
 
// Function to return the number of
// make the array sorted
static void countShift(int arr[], int n,
                       Vector<Vector<Integer> > queries)
{
  for (Vector<Integer> q : queries)
  {
    // Index x to update
    int index = q.get(0);
 
    // Increment value by y
    int update = q.get(1);
 
    // Set newElement equals
    // to x + y
    int newElement = arr[index] + update;
 
    // Compute the new index
    int newIndex = computePos(arr, n,
                              newElement);
 
    // Print the minimum number
    // of swaps
    System.out.print(Math.abs(newIndex -
                              index) + " ");
  }
}
 
// Driver Code
public static void main(String[] args)
{
  // Given array arr[]
  int arr[] = {2, 3, 4, 5, 6};
 
  int N = arr.length;
 
  // Given Queries
  Vector<Vector<Integer> > queries =
                new Vector<>();
  Vector<Integer> v =
         new Vector<>();
  Vector<Integer> v1 =
         new Vector<>();
   
  v.add(0);
  v.add(-1);
  queries.add(v);
  v1.add(4);
  v1.add(-11);
  queries.add(v1);
 
  // Function Call
  countShift(arr, N, queries);
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program for the above approach
 
# Function to return the position of
# the given value using binary search
def computePos(arr, n, value):
     
    # Return 0 if every value is
    # greater than the given value
    if (value < arr[0]):
        return 0
 
    # Return N-1 if every value is
    # smaller than the given value
    if (value > arr[n - 1]):
        return n - 1
  
    # Perform Binary Search
    start = 0
    end = n - 1
 
    # Iterate till start < end
    while (start < end):
 
        # Find the mid
        mid = (start + end + 1) // 2
 
        # Update start and end
        if (arr[mid] >= value):
            end = mid - 1
        else:
            start = mid
 
    # Return the position of
    # the given value
    return start
 
# Function to return the number of
# make the array sorted
def countShift(arr, n, queries):
 
    for q in queries:
         
        # Index x to update
        index = q[0]
 
        # Increment value by y
        update = q[1]
 
        # Set newElement equals
        # to x + y
        newElement = arr[index] + update
 
        # Compute the new index
        newIndex = computePos(arr, n, newElement)
 
        # Print the minimum number
        # of swaps
        print(abs(newIndex - index), end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    # Given array arr[]
    arr = [ 2, 3, 4, 5, 6 ]
 
    N = len(arr)
 
    # Given Queries
    queries = [ [ 0, -1 ], [4, -11 ] ]
 
    # Function Call
    countShift(arr, N, queries)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to return the position of
// the given value using binary search
static int computePos(int []arr,
                      int n, int value)
{
  // Return 0 if every value is
  // greater than the given value
  if (value < arr[0])
    return 0;
 
  // Return N-1 if every value is
  // smaller than the given value
  if (value > arr[n - 1])
    return n - 1;
 
  // Perform Binary Search
  int start = 0;
  int end = n - 1;
 
  // Iterate till start
  // < end
  while (start < end)
  {
    // Find the mid
    int mid = (start +
               end + 1) / 2;
 
    // Update start and end
    if (arr[mid] >= value)
      end = mid - 1;
    else
      start = mid;
  }
 
  // Return the position of
  // the given value
  return start;
}
 
// Function to return the number of
// make the array sorted
static void countShift(int []arr, int n,
                       List<List<int> >
                       queries)
{
  foreach (List<int> q in queries)
  {
    // Index x to update
    int index = q[0];
 
    // Increment value by y
    int update = q[1];
 
    // Set newElement equals
    // to x + y
    int newElement = arr[index] +
                     update;
 
    // Compute the new index
    int newIndex = computePos(arr, n,
                              newElement);
 
    // Print the minimum number
    // of swaps
    Console.Write(Math.Abs(newIndex -
                           index) + " ");
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given array []arr
  int []arr = {2, 3, 4, 5, 6};
 
  int N = arr.Length;
 
  // Given Queries
  List<List<int> > queries =
            new List<List<int>>();
  List<int> v =
       new List<int>();
  List<int> v1 =
       new List<int>();
 
  v.Add(0);
  v.Add(-1);
  queries.Add(v);
  v1.Add(4);
  v1.Add(-11);
  queries.Add(v1);
 
  // Function Call
  countShift(arr, N, queries);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to return the position of
// the given value using binary search
function computePos(arr, n, value)
{
    // Return 0 if every value is
    // greater than the given value
    if (value < arr[0])
        return 0;
 
    // Return N-1 if every value is
    // smaller than the given value
    if (value > arr[n - 1])
        return n - 1;
 
    // Perform Binary Search
    var start = 0;
    var end = n - 1;
 
    // Iterate till start < end
    while (start < end) {
 
        // Find the mid
        var mid = parseInt((start + end + 1) / 2);
 
        // Update start and end
        if (arr[mid] >= value)
            end = mid - 1;
        else
            start = mid;
    }
 
    // Return the position of
    // the given value
    return start;
}
 
// Function to return the number of
// make the array sorted
function countShift(arr, n, queries)
{
    for(var i =0; i< queries.length; i++)
    {
        // Index x to update
        var index = queries[i][0];
 
        // Increment value by y
        var update = queries[i][1];
 
        // Set newElement equals
        // to x + y
        var newElement = arr[index]
                         + update;
 
        // Compute the new index
        var newIndex = computePos(
            arr, n, newElement);
 
        // Print the minimum number
        // of swaps
        document.write( Math.abs(newIndex - index)
             + " ");
    }
}
 
// Driver Code
// Given array arr[]
var arr = [ 2, 3, 4, 5, 6 ];
var N = arr.length;
 
// Given Queries
var queries = [[ 0, -1 ], [ 4, -11 ]];
 
// Function Call
countShift(arr, N, queries);
 
</script>
Producción: 

0 4

 

Complejidad de tiempo: O(Q*N*log N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por ApurvaRaj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *