Сумма минимальной разницы между последовательными элементами массива

Опубликовано: 7 Января, 2022

Учитывая массив пар, где каждая пара представляет собой диапазон, задача состоит в том, чтобы найти сумму минимальной разницы между последовательными элементами массива, в котором массив заполнен следующим образом:

  • Каждый элемент массива находится в диапазоне, заданном соответствующим индексом в массиве диапазонов.
  • Итоговая сумма разницы последовательных элементов в сформированном массиве минимальна.

Примеры:

Input: range[] = {{2, 4}, {3, 6}, {1, 5}, {1, 3}, {2, 7}} 
Output: 0 
The result is 0 because the array {3, 3, 3, 3, 3} is choosen 
then the sum of difference of consecutive element will be 
{ |3-3| + |3-3| + |3-3| + |3-3| } = 0 which the minimum. 
Input: range[] = {{1, 3}, {2, 5}, {6, 8}, {1, 2}, {2, 3}} 
Output: 7 
The result is 7 because if the array {3, 3, 6, 2, 2} is choosen 
then the sum of difference of consecutive element will be 
{ |3-3| + |6-3| + |2-6| + |2-2| }= 7 which is the minimum.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: был применен жадный подход к решению вышеуказанной проблемы. Изначально мы должны заполнить массив таким образом, чтобы сумма полученной разницы была минимальной. Жадный подход заключается в следующем:

  • Если диапазон предыдущего индекса пересекает диапазон текущего индекса, то в этом случае минимальная разница будет равна 0 и сохранит самое высокое значение и наименьшее значение пересекающегося диапазона.
  • Если наименьшее значение диапазона предыдущего индекса больше, чем наибольшее значение для текущего индекса, то в этом случае наименьшая возможная сумма - это разница между наименьшим значением предыдущего диапазона и наибольшим значением, сохраненным в текущем диапазоне.
  • Если самый высокий диапазон предыдущего индекса ниже самого низкого значения текущего диапазона, тогда минимальная сумма - это разница между самым низким значением, сохраненным для текущего индекса, и самым высоким диапазоном предыдущего индекса.

Below is the implementation of the above approach: 
 

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;
 
    // inititalize 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];
 
    // inititalize 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
 
    # inititalize 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];
 
    // inititalize 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];
 
// inititalize 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];
C++ Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

С++ Std против Stl
20 Февраля, 2023
C++ функция __builtin_popcount()
20 Февраля, 2023
Как получить доступ к элементам в наборе по индексу в С++?
20 Февраля, 2023
Строка С++ для плавающей/двойной и наоборот
20 Февраля, 2023
Преобразование шестнадцатеричной строки в целое число со знаком в С++
20 Февраля, 2023
C++ функция getenv()
20 Февраля, 2023
Вложенный, если в C++
20 Февраля, 2023
C++ вектор структур
20 Февраля, 2023