Рубрики

Минимальная начальная энергия, необходимая для пересечения улицы

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

Примечание . Значение минимальной начальной требуемой энергии будет равно 1, даже если мы успешно перейдем улицу, не потеряв энергии до значения, меньшего и равного 0 в любой контрольной точке. 1 требуется для начальной контрольной точки.

Примеры :

Input : arr[] = {4, -10, 4, 4, 4}
Output: 7
Suppose initially we have energy = 0, now at 1st
checkpoint, we get 4. At 2nd checkpoint, energy gets
reduced by -10 so we have 4 + (-10) = -6 but at any 
checkpoint value of energy can not less than equals 
to 0. So initial energy must be at least 7 because
having 7 as initial energy value at 1st checkpoint
our energy will be = 7+4 = 11 and then we can cross 
2nd checkpoint successfully. Now after 2nd checkpoint,
all checkpoint have positive value so we can cross 
street successfully with 7 initial energy.

Input : arr[] = {3, 5, 2, 6, 1}
Output: 1
We need at least 1 initial energy to reach first
checkpoint

Input : arr[] = {-1, -5, -9}
Output: 16

Мы берем начальную минимальную энергию 0 т.е. initMinEnergy = 0 и энергия в любой контрольной точке как currEnergy = 0. Теперь проходите каждую контрольную точку линейно и добавляйте уровень энергии в каждой i-й контрольной точке, т.е. currEnergy = currEnergy + arr [i]. Если currEnergy становится неположительным, то для пересечения этой точки нам понадобится как минимум «abs (currEnergy) + 1» дополнительная начальная энергия. Поэтому мы обновляем initMinEnergy = (initMinEnergy + abs (currEnergy) + 1). Мы также обновляем currEnergy = 1, так как теперь у нас есть необходимая дополнительная минимальная начальная энергия для следующей точки.

Ниже приведена реализация вышеуказанной идеи.

C / C ++

// C ++ программа для поиска минимальной начальной энергии для
// достигнуть конца
#include<bits/stdc++.h>

using namespace std;

  
// Функция для расчета минимальной начальной энергии
// arr [] запасает энергию на каждой контрольной точке на улице

int minInitialEnergy(int arr[], int n)

{

    // initMinEnergy - переменная для хранения минимального начального значения

    // энергия требуется.

    int initMinEnergy = 0;

  

    // currEnergy является переменной для хранения текущего значения

    // энергия на контрольно-пропускном пункте на улице

    int currEnergy = 0;

  

    // флаг, чтобы проверить, успешно ли мы пересекли

    // улица без потерь энергии <= o в любом пункте пропуска

    bool flag = 0;

  

    // Обходим каждую контрольную точку линейно

    for (int i=0; i<n; i++)

    {

        currEnergy += arr[i];

  

        // Если текущая энергия становится отрицательной или 0, приращение

        // начальная минимальная энергия по отрицательному значению плюс 1.

        // сохранить текущую энергию положительной (не менее 1). Также

        // обновляем текущую энергию и флаг.

        if (currEnergy <= 0)

        {

            initMinEnergy += abs(currEnergy) +1;

            currEnergy = 1;

            flag = 1;

        }

    }

  

    // Если энергия никогда не становилась отрицательной или равной 0, тогда

    // возвращаем 1. остальное возвращаем вычисленное initMinEnergy

    return (flag == 0)? 1 : initMinEnergy;

}

  
// Программа Driver для тестирования кейса

int main()

{

    int arr[] = {4, -10, 4, 4, 4};

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << minInitialEnergy(arr, n);

    return 0;

}

Джава

// Java программа для поиска минимума
// начальная энергия для достижения конца

  

class GFG {

      
// Функция для расчета минимума
// начальная энергия arr [] сохраняет энергию
// на каждом контрольно-пропускном пункте на улице

static int minInitialEnergy(int arr[], int n) 

{

    // initMinEnergy - переменная для хранения

    // минимальная начальная энергия требуется.

    int initMinEnergy = 0;

  

    // currEnergy - переменная для хранения

    // текущее значение энергии при

    // я контрольно-пропускной пункт на улице

    int currEnergy = 0;

  

    // флаг, чтобы проверить, если мы успешно

    // пересек улицу без энергии

    // потеря <= o в любой контрольной точке

    boolean flag = false;

  

    // Обходим каждую контрольную точку линейно

    for (int i = 0; i < n; i++) {

    currEnergy += arr[i];

  

    // Если текущая энергия становится отрицательной или 0,

    // увеличиваем начальную минимальную энергию на отрицательную

    // значение плюс 1. сохранить текущую энергию

    // положительно (не менее 1). Также

    // обновляем текущую энергию и флаг.

    if (currEnergy <= 0) {

        initMinEnergy += Math.abs(currEnergy) + 1;

        currEnergy = 1;

        flag = true;

    }

    }

  

    // Если энергия никогда не становилась отрицательной или равной 0, тогда

    // возвращаем 1. остальное возвращаем вычисленное initMinEnergy

    return (flag == false) ? 1 : initMinEnergy;

}

  
// Код драйвера

public static void main(String[] args)

{

    int arr[] = {4, -10, 4, 4, 4};

    int n = arr.length;

    System.out.print(minInitialEnergy(arr, n));

}
}

  
// Этот код предоставлен Anant Agarwal.

питон

# Программа Python для поиска минимальной начальной энергии для
# достичь конца

  
# Функция для расчета минимальной начальной энергии
# arr [] активирует энергию на каждом контрольно-пропускном пункте на улице

def minInitialEnergy(arr):

    n = len(arr)

      

    # initMinEnergy - переменная для хранения минимального начального значения

    # энергия требуется

    initMinEnergy = 0;

      

    # currEnery переменная для хранения текущего значения

    # Энерджи на контрольно-пропускном пункте на улице

    currEnergy = 0 

  

    # флаг, чтобы проверить, успешно ли мы пересекли

    # улица без потерь энергии <= 0 в любом пункте пропуска

    flag = 0 

      

    # Обходить каждую контрольную точку линейно

    for i in range(n):

        currEnergy += arr[i]

          

        # Если текущая энергия становится отрицательной или равна 0, приращение

        # начальная минимальная энергия по отрицательному значению плюс 1.

        # поддерживать текущую энергию положительной (не менее 1). Также

        # обновить текущую энергию и флаг.

        if currEnergy <= 0 :

            initMinEnergy += (abs(currEnergy) +1)

            currEnergy = 1 

            flag = 1

  

    # Если энергия никогда не становилась отрицательной или равной 0, то

    # return 1. В противном случае возвращаем вычисленное initMinEnergy

    return 1 if flag == 0 else initMinEnergy

  

  
# Программа драйвера для проверки вышеуказанной функции

arr = [4, -10 , 4, 4, 4]

print minInitialEnergy(arr)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для поиска минимума
// C # программа для поиска минимума
// начальная энергия для достижения конца

using System;

  

class GFG {

      
// Функция для расчета минимума
// начальная энергия arr [] сохраняет энергию
// на каждом контрольно-пропускном пункте на улице

static int minInitialEnergy(int []arr, int n) 

{

      

    // initMinEnergy - переменная для хранения

    // минимальная начальная энергия требуется.

    int initMinEnergy = 0;

  

    // currEnergy - переменная для хранения

    // текущее значение энергии при

    // я контрольно-пропускной пункт на улице

    int currEnergy = 0;

  

    // флаг, чтобы проверить, если мы успешно

    // пересек улицу без энергии

    // потеря <= o в любой контрольной точке

    bool flag = false;

  

    // Обходим каждую контрольную точку линейно

    for (int i = 0; i < n; i++) {

    currEnergy += arr[i];

  

    // Если текущая энергия становится отрицательной или 0,

    // отрицательный начальный минимум энергии

    // по значению плюс 1. сохранить текущий

    // энергия положительная (минимум 1). Также

    // обновляем текущую энергию и флаг.

    if (currEnergy <= 0)

    {

        initMinEnergy += Math.Abs(currEnergy) + 1;

        currEnergy = 1;

        flag = true;

    }

    }

  

    // Если энергия никогда не становилась отрицательной

    // или 0, затем возвращаем 1. Остальное возвращаем

    // вычислил initMinEnergy

    return (flag == false) ? 1 : initMinEnergy;

}

  
// Код драйвера

public static void Main()

{

    int []arr = {4, -10, 4, 4, 4};

    int n = arr.Length;

    Console.Write(minInitialEnergy(arr, n));

}
}

  
// Этот код предоставлен Нитином Митталом.

PHP

<?php
// PHP программа для поиска минимума
// начальная энергия для достижения конца

  
// Функция для расчета минимума
// начальная энергия arr [] store
// энергия на каждом контрольно-пропускном пункте на улице

function minInitialEnergy($arr, $n)

{

    // initMinEnergy является переменной

    // хранить минимальный начальный

    // энергия требуется.

    $initMinEnergy = 0;

  

    // currEnergy является переменной для

    // сохранить текущую стоимость энергии

    // на своем контрольно-пропускном пункте на улице

    $currEnergy = 0;

  

    // флаг, чтобы проверить, есть ли у нас

    // успешно пересек

    // улица без энергии

    // потеря <= o в любой контрольной точке

    $flag = 0;

  

    // Обходим каждую проверку

    // указать линейно

    for ($i = 0; $i < $n; $i++)

    {

        $currEnergy += $arr[$i];

  

        // Если текущая энергия становится

        // отрицательный или 0, приращение

        // начальная минимальная энергия

        // отрицательное значение плюс 1.

        // сохранить текущую энергию

        // положительно (не менее 1). Также

        // обновляем текущую энергию и флаг.

        if ($currEnergy <= 0)

        {

            $initMinEnergy += abs($currEnergy) + 1;

            $currEnergy = 1;

            $flag = 1;

        }

    }

  

    // Если энергия никогда не стала

    // отрицательный или 0, тогда

    // возвращаем 1. остальное возвращаем

    // вычислил initMinEnergy

    return ($flag == 0) ? 1 : $initMinEnergy;

}

  
// Код драйвера

$arr = array(4, -10, 4, 4, 4);

$n = sizeof($arr);

echo minInitialEnergy($arr, $n);

  
// Этот код добавлен
// нитин митталь.
?>


Выход :

7

Сложность времени: O (n)
Вспомогательное пространство: O (1)

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Минимальная начальная энергия, необходимая для пересечения улицы

0.00 (0%) 0 votes