Dada una array de pares donde cada par representa un rango, la tarea es encontrar la suma de la diferencia mínima entre los elementos consecutivos de una array donde la array se llena de la siguiente manera:
- Cada elemento de una array se encuentra en el rango dado en su índice correspondiente en la array de rango.
- La suma final de la diferencia de elementos consecutivos en la array formada es mínima.
Ejemplos:
Entrada: range[] = {{2, 4}, {3, 6}, {1, 5}, {1, 3}, {2, 7}}
Salida: 0
El resultado es 0 porque la array {3, 3, 3, 3, 3} se elige
entonces la suma de la diferencia del elemento consecutivo será
{ |3-3| + |3-3| + |3-3| + |3-3| } = 0 que el mínimo.
Entrada: range[] = {{1, 3}, {2, 5}, {6, 8}, {1, 2}, {2, 3}}
Salida: 7
El resultado es 7 porque si la array {3 , 3, 6, 2, 2}
entonces la suma de la diferencia de elementos consecutivos será
{ |3-3| + |6-3| + |2-6| + |2-2| }= 7 que es el mínimo.
Enfoque: Se ha seguido un enfoque codicioso para resolver el problema anterior. Inicialmente, tenemos que llenar la array de tal manera que la suma de la diferencia obtenida sea mínima. El enfoque codicioso es el siguiente:
- Si el rango del índice anterior se cruza con el rango del índice actual, en este caso, la diferencia mínima será 0 y almacenará el valor más alto y el valor más bajo del rango que se cruza.
- Si el valor más bajo del rango del índice anterior es mayor que el valor más alto del índice actual, en este caso la menor suma posible es la diferencia entre el valor más bajo del rango anterior y el valor más alto almacenado en el rango actual.
- Si el rango más alto del índice anterior es menor que el valor más bajo del rango actual, la suma mínima es la diferencia entre el valor más bajo almacenado para el índice actual y el rango más alto del índice anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for finding the minimum sum of
// difference between consecutive elements
#include <bits/stdc++.h>
using namespace std;
// function to find minimum sum of
// difference of consecutive element
int solve(pair<int, int> v[], int n)
{
// ul to store upper limit
// ll to store lower limit
int ans, ul, ll;
// storethe lower range in ll
// and upper range in ul
ll = v[0].first;
ul = v[0].second;
// initialize the answer with 0
ans = 0;
// iterate for all ranges
for (int i = 1; i < n; i++) {
// case 1, in this case the difference will be 0
if ((v[i].first <= ul && v[i].first >= ll) ||
(v[i].second >= ll && v[i].second <= ul)) {
// change upper limit and lower limit
if (v[i].first > ll) {
ll = v[i].first;
}
if (v[i].second < ul) {
ul = v[i].second;
}
}
// case 2
else if (v[i].first > ul) {
// store the difference
ans += abs(ul - v[i].first);
ul = v[i].first;
ll = v[i].first;
}
// case 3
else if (v[i].second < ll) {
// store the difference
ans += abs(ll - v[i].second);
ul = v[i].second;
ll = v[i].second;
}
}
return ans;
}
// Driver code
int main()
{
// array of range
pair<int, int> v[] = { { 1, 3 }, { 2, 5 },
{ 6, 8 }, { 1, 2 }, { 2, 3 } };
int n = sizeof(v) / sizeof(v[0]);
cout << solve(v, n) << endl;
return 0;
}
Java
// Java program for finding the
// minimum sum of difference
// between consecutive elements
import java.io.*;
class GFG
{
// function to find minimum
// sum of difference of
// consecutive element
static int solve(int[][] v, int n)
{
// ul to store upper limit
// ll to store lower limit
int ans, ul, ll;
int first = 0;
int second = 1;
// storethe lower range
// in ll and upper range
// in ul
ll = v[0][first];
ul = v[0][second];
// initialize the
// answer with 0
ans = 0;
// iterate for all ranges
for (int i = 1; i < n; i++)
{
// case 1, in this case
// the difference will be 0
if ((v[i][first] <= ul &&
v[i][first] >= ll) ||
(v[i][second] >= ll &&
v[i][second] <= ul))
{
// change upper limit
// and lower limit
if (v[i][first] > ll)
{
ll = v[i][first];
}
if (v[i][second] < ul)
{
ul = v[i][second];
}
}
// case 2
else if (v[i][first] > ul)
{
// store the difference
ans += Math.abs(ul - v[i][first]);
ul = v[i][first];
ll = v[i][first];
}
// case 3
else if (v[i][second] < ll)
{
// store the difference
ans += Math.abs(ll - v[i][second]);
ul = v[i][second];
ll = v[i][second];
}
}
return ans;
}
// Driver code
public static void main(String []args)
{
// array of range
int[][] v = {{ 1, 3 }, { 2, 5 },
{ 6, 8 }, { 1, 2 },
{ 2, 3 }};
int n = 5;
System.out.println(solve(v, n));
}
}
// This code is contributed
// by chandan_jnu
Python
# Python program for finding # the minimum sum of difference # between consecutive elements class pair: first = 0 second = 0 def __init__(self, a, b): self.first = a self.second = b # function to find minimum # sum of difference of # consecutive element def solve(v, n): # ul to store upper limit # ll to store lower limit ans = 0; ul = 0; ll = 0; # storethe lower range # in ll and upper range # in ul ll = v[0].first ul = v[0].second # initialize the # answer with 0 ans = 0 # iterate for all ranges for i in range(1, n): # case 1, in this case # the difference will be 0 if (v[i].first <= ul and v[i].first >= ll) or \ (v[i].second >= ll and v[i].second <= ul): # change upper limit # and lower limit if v[i].first > ll: ll = v[i].first if v[i].second < ul: ul = v[i].second; # case 2 elif v[i].first > ul: # store the difference ans += abs(ul - v[i].first) ul = v[i].first ll = v[i].first # case 3 elif v[i].second < ll: # store the difference ans += abs(ll - v[i].second); ul = v[i].second; ll = v[i].second; return ans # Driver code # array of range v = [pair(1, 3), pair(2, 5), pair(6, 8), pair(1, 2), pair(2, 3) ] n = len(v) print(solve(v, n)) # This code is contributed # by Harshit Saini
C#
// C# program for finding the
// minimum sum of difference
// between consecutive elements
using System;
class GFG
{
// function to find minimum
// sum of difference of
// consecutive element
static int solve(int[,] v, int n)
{
// ul to store upper limit
// ll to store lower limit
int ans, ul, ll;
int first = 0;
int second = 1;
// storethe lower range
// in ll and upper range
// in ul
ll = v[0, first];
ul = v[0, second];
// initialize the
// answer with 0
ans = 0;
// iterate for all ranges
for (int i = 1; i < n; i++)
{
// case 1, in this case
// the difference will be 0
if ((v[i, first] <= ul &&
v[i, first] >= ll) ||
(v[i, second] >= ll &&
v[i, second] <= ul))
{
// change upper limit
// and lower limit
if (v[i, first] > ll)
{
ll = v[i, first];
}
if (v[i, second] < ul)
{
ul = v[i, second];
}
}
// case 2
else if (v[i, first] > ul)
{
// store the difference
ans += Math.Abs(ul - v[i, first]);
ul = v[i, first];
ll = v[i, first];
}
// case 3
else if (v[i, second] < ll)
{
// store the difference
ans += Math.Abs(ll - v[i, second]);
ul = v[i, second];
ll = v[i, second];
}
}
return ans;
}
// Driver code
static void Main()
{
// array of range
int[,] v = new int[5,2]{ { 1, 3 }, { 2, 5 },
{ 6, 8 }, { 1, 2 },
{ 2, 3 } };
int n = 5;
Console.WriteLine(solve(v, n));
}
}
// This code is contributed
// by chandan_jnu
PHP
<?php
// PHP program for finding the
// minimum sum of difference
// between consecutive elements
// function to find minimum
// sum of difference of
// consecutive element
function solve($v, $n)
{
// ul to store upper limit
// ll to store lower limit
$ans; $ul; $ll;
$first = 0;
$second = 1;
// storethe lower range
// in ll and upper range
// in ul
$ll = $v[0][$first];
$ul = $v[0][$second];
// initialize the
// answer with 0
$ans = 0;
// iterate for all ranges
for ($i = 1; $i <$n; $i++)
{
// case 1, in this case
// the difference will be 0
if (($v[$i][$first] <= $ul and
$v[$i][$first] >= $ll) or
($v[$i][$second] >= $ll and
$v[$i][$second] <= $ul))
{
// change upper limit
// and lower limit
if ($v[$i][$first] > $ll)
{
$ll = $v[$i][$first];
}
if ($v[$i][$second] < $ul)
{
$ul = $v[$i][$second];
}
}
// case 2
else if ($v[$i][$first] > $ul)
{
// store the difference
$ans += abs($ul - $v[$i][$first]);
$ul = $v[$i][$first];
$ll = $v[$i][$first];
}
// case 3
else if ($v[$i][$second] < $ll)
{
// store the difference
$ans += abs($ll - $v[$i][$second]);
$ul = $v[$i][$second];
$ll = $v[$i][$second];
}
}
return $ans;
}
// Driver code
// array of range
$v = array(array( 1, 3 ),
array( 2, 5 ),
array( 6, 8 ),
array( 1, 2 ),
array( 2, 3 ));
$n = 5;
echo(solve($v, $n));
// This code is contributed
// by chandan_jnu
?>
Javascript
<script>
// JavaScript program for finding the
// minimum sum of difference
// between consecutive elements
// function to find minimum
// sum of difference of
// consecutive element
function solve(v, n)
{
// ul to store upper limit
// ll to store lower limit
let ans, ul, ll;
let first = 0;
let second = 1;
// storethe lower range
// in ll and upper range
// in ul
ll = v[0][first];
ul = v[0][second];
// initialize the
// answer with 0
ans = 0;
// iterate for all ranges
for (let i = 1; i < n; i++)
{
// case 1, in this case
// the difference will be 0
if ((v[i][first] <= ul &&
v[i][first] >= ll) ||
(v[i][second] >= ll &&
v[i][second] <= ul))
{
// change upper limit
// and lower limit
if (v[i][first] > ll)
{
ll = v[i][first];
}
if (v[i][second] < ul)
{
ul = v[i][second];
}
}
// case 2
else if (v[i][first] > ul)
{
// store the difference
ans += Math.abs(ul - v[i][first]);
ul = v[i][first];
ll = v[i][first];
}
// case 3
else if (v[i][second] < ll)
{
// store the difference
ans += Math.abs(ll - v[i][second]);
ul = v[i][second];
ll = v[i][second];
}
}
return ans;
}
// driver code
let v = [[ 1, 3 ], [ 2, 5 ],
[ 6, 8 ], [ 1, 2 ],
[ 2, 3 ]];
let n = 5;
document.write(solve(v, n));
</script>
Producción:
7
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Aman Goyal 2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA