Distancia mínima para visitar puntos K dados en el eje X después de comenzar desde el origen

Posted on by Rudeus Greyrat

Dada una array ordenada , arr[] de tamaño N que representa las posiciones del i -ésimo punto en el eje X y un número entero K , la tarea es encontrar la distancia mínima requerida para viajar para visitar el punto K comenzando desde el origen de X- eje.

Ejemplos:

Entrada: arr[]={-30, -10, 10, 20, 50}, K = 3
Salida: 40 
Explicación: 
Pasar del origen al segundo punto. Por lo tanto, la distancia total recorrida = 10. 
Pasando del segundo punto al tercer punto. Por lo tanto, recorrido total = 10 + 10 = 20 
Moviéndose del tercer punto al cuarto punto. Por lo tanto, distancia total recorrida = 20 + 20 = 40 
Por lo tanto, la distancia total recorrida para visitar el punto K es 40. 

Entrada: arr[]={-1, -5, -4, -3, 6}, K = 3
Salida: 6

Planteamiento: El problema se puede resolver visitando cada K punto consecutivo e imprimiendo la distancia mínima recorrida para visitar K puntos consecutivos. Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, digamos res , para almacenar la distancia mínima recorrida para visitar el punto K.
  • Inicialice una variable, digamos dist , para almacenar la distancia recorrida para visitar K puntos.
  • Atraviese la array y verifique las siguientes condiciones. 
    • Si el valor de (arr[i] >= 0 y arr[i + K -1] >= 0) es verdadero, actualice dist = max(arr[i], arr[i + K -1]).
    • De lo contrario, dist = abs(arr[i]) + abs(arr[i + K – 1]) + min(abs(arr[i]), abs(arr[i + K – 1])) .
    • Finalmente, actualice res = min(res, dist) .
  • Finalmente, imprima el valor de res .

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

C++

// C++ program to implement
// the above approach
   
#include <bits/stdc++.h>
using namespace std;
   
   
// Function to find the minimum distance 
// travelled to visit K point
int MinDistK(int arr[], int N, int K)
{
       
       
    // Stores minimum distance travelled
    // to visit K point
    int res = INT_MAX;
       
       
    // Stores distance travelled
    // to visit points
    int dist = 0;
       
    // Traverse the array arr[]
    for (int i = 0; i <= (N - K); i++) {
           
           
       // If arr[i] and arr[i + K - 1]
       // are positive
        if (arr[i] >= 0  && 
              arr[i + K - 1] >= 0) {
           
           
            // Update dist
            dist = max(arr[i], arr[i + K - 1]);
        }
        else {
               
               
            // Update dist
            dist = abs(arr[i]) +
                   abs(arr[i + K - 1])
                  + min(abs(arr[i]),
                        abs(arr[i + K - 1]));
        }
           
           
        // Update res
        res = min(res, dist);
    }
       
    return res;
}
   
   
// Driver Code
int main()
{
   
    int K = 3;
    // initial the array
    int arr[] = { -30, -10, 10, 20, 50 };
       
    int N = sizeof(arr) / sizeof(arr[0]);
   
    cout<< MinDistK(arr, N, K);
}

Java

// Java program to implement
// the above approach
import java.util.*;
class solution{
   
// Function to find the minimum
// distance travelled to visit
// K point
static int MinDistK(int arr[],
                    int N, int K)
{      
  // Stores minimum distance
  // travelled to visit K point
  int res = Integer.MAX_VALUE;
 
  // Stores distance travelled
  // to visit points
  int dist = 0;
 
  // Traverse the array arr[]
  for (int i = 0;
           i <= (N - K); i++)
  {
    // If arr[i] and arr[i + K - 1]
    // are positive
    if (arr[i] >= 0  && 
        arr[i + K - 1] >= 0)
    {
      // Update dist
      dist = Math.max(arr[i],
                      arr[i + K - 1]);
    }
    else
    {
      // Update dist
      dist = Math.abs(arr[i]) +
             Math.abs(arr[i + K - 1]) +
             Math.min(Math.abs(arr[i]),
             Math.abs(arr[i + K - 1]));
    }
 
    // Update res
    res = Math.min(res, dist);
  }
 
  return res;
}
   
// Driver Code
public static void main(String args[])
{
  int K = 3;
  // initial the array
  int arr[] = {-30, -10,
               10, 20, 50};
 
  int N = arr.length;
  System.out.println(MinDistK(arr, N, K));
}
}
   
// This code is contributed by bgangwar59

Python3

# Python3 program to implement
# the above approach
import sys
 
# Function to find the minimum distance 
# travelled to visit K point
def MinDistK(arr, N, K):
     
    # Stores minimum distance travelled
    # to visit K point
    res = sys.maxsize
     
    # Stores distance travelled
    # to visit points
    dist = 0
     
    # Traverse the array arr[]
    for i in range(N - K + 1):
         
        # If arr[i] and arr[i + K - 1]
        # are positive
        if (arr[i] >= 0 and arr[i + K - 1] >= 0):
             
            # Update dist
            dist = max(arr[i], arr[i + K - 1])
        else:
             
            # Update dist
            dist = (abs(arr[i]) + abs(arr[i + K - 1]) +
                min(abs(arr[i]), abs(arr[i + K - 1])))
           
        # Update res
        res = min(res, dist)
       
    return res
   
# Driver Code
if __name__ == '__main__':
     
    K = 3
     
    # Initial the array
    arr = [ -30, -10, 10, 20, 50 ]
       
    N = len(arr)
   
    print(MinDistK(arr, N, K))
     
# This code is contributed by ipg2016107

C#

// C# program to implement
// the above approach 
using System;
 
class GFG{
    
// Function to find the minimum
// distance travelled to visit
// K point
static int MinDistK(int[] arr,
                    int N, int K)
{ 
   
  // Stores minimum distance
  // travelled to visit K point
  int res = Int32.MaxValue;
  
  // Stores distance travelled
  // to visit points
  int dist = 0;
  
  // Traverse the array arr[]
  for(int i = 0; i <= (N - K); i++)
  {
     
    // If arr[i] and arr[i + K - 1]
    // are positive
    if (arr[i] >= 0 && 
        arr[i + K - 1] >= 0)
    {
       
      // Update dist
      dist = Math.Max(arr[i],
                      arr[i + K - 1]);
    }
    else
    {
       
      // Update dist
      dist = Math.Abs(arr[i]) +
             Math.Abs(arr[i + K - 1]) +
             Math.Min(Math.Abs(arr[i]),
             Math.Abs(arr[i + K - 1]));
    }
  
    // Update res
    res = Math.Min(res, dist);
  }
  return res;
}
    
// Driver Code
public static void Main()
{
  int K = 3;
   
  // Initial the array
  int[] arr = { -30, -10, 10, 20, 50};
  
  int N = arr.Length;
   
  Console.WriteLine(MinDistK(arr, N, K));
}
}
 
// This code is contributed by code_hunt

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to find the minimum
// distance travelled to visit
// K point
function MinDistK(arr, N, K)
{     
  // Stores minimum distance
  // travelled to visit K point
  let res = Number.MAX_VALUE;
  
  // Stores distance travelled
  // to visit points
  let dist = 0;
  
  // Traverse the array arr[]
  for (let i = 0;
           i <= (N - K); i++)
  {
    // If arr[i] and arr[i + K - 1]
    // are positive
    if (arr[i] >= 0  &&
        arr[i + K - 1] >= 0)
    {
      // Update dist
      dist = Math.max(arr[i],
                      arr[i + K - 1]);
    }
    else
    {
      // Update dist
      dist = Math.abs(arr[i]) +
             Math.abs(arr[i + K - 1]) +
             Math.min(Math.abs(arr[i]),
             Math.abs(arr[i + K - 1]));
    }
  
    // Update res
    res = Math.min(res, dist);
  }
  
  return res;
}
 
// Driver Code
 
    let K = 3;
  // initial the array
  let arr = [-30, -10,
               10, 20, 50];
  
  let N = arr.length;
  document.write(MinDistK(arr, N, K));
      
</script>
Producción

40

Complejidad de tiempo: O (NK), donde n es la longitud de la array dada para el valor de K dado.
Espacio Auxiliar:O(1)

Publicación traducida automáticamente

Artículo escrito por grand_master 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 *