算法设计：过马路所需的最低初始能量

2021年3月10日16:18:05 发表评论 1,059 次浏览

本文概述

给定一个包含正数和负数的数组。该数组表示从街道的一端到另一端的检查点。正值和负值表示该检查点的能量。正数增加能量, 负数减少。找到过马路所需的最小初始能量, 以使能量水平永远不会变为0或小于0。

注意 ：即使我们成功过马路而在任何检查点都没有将能量损失到小于等于0, 所需的最小初始能量的值为1。初始检查点需要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++ program to find minimum initial energy to
// reach end
#include<bits/stdc++.h>
using namespace std;
  
// Function to calculate minimum initial energy
// arr[] stores energy at each checkpoints on street
int minInitialEnergy( int arr[], int n)
{
     // initMinEnergy is variable to store minimum initial
     // energy required.
     int initMinEnergy = 0;
  
     // currEnergy is variable to store current value of
     // energy at i'th checkpoint on street
     int currEnergy = 0;
  
     // flag to check if we have successfully crossed the
     // street without any energy loss <= o at any checkpoint
     bool flag = 0;
  
     // Traverse each check point lineraly
     for ( int i=0; i<n; i++)
     {
         currEnergy += arr[i];
  
         // If current energy, becomes negative or 0, increment
         // initial minimum energy by the negative value plus 1.
         // to keep current energy positive (at least 1). Also
         // update current energy and flag.
         if (currEnergy <= 0)
         {
             initMinEnergy += abs (currEnergy) +1;
             currEnergy = 1;
             flag = 1;
         }
     }
  
     // If energy never became negative or 0, then
     // return 1. Else return computed initMinEnergy
     return (flag == 0)? 1 : initMinEnergy;
}
  
// Driver Program to test the case
int main()
{
     int arr[] = {4, -10, 4, 4, 4};
     int n = sizeof (arr)/ sizeof (arr[0]);
     cout << minInitialEnergy(arr, n);
     return 0;
}

Java

// Java program to find minimum 
// initial energy to reach end
  
class GFG {
      
// Function to calculate minimum 
// initial energy arr[] stores energy
// at each checkpoints on street
static int minInitialEnergy( int arr[], int n) 
{
     // initMinEnergy is variable to store 
     // minimum initial energy required.
     int initMinEnergy = 0 ;
  
     // currEnergy is variable to store 
     // current value of energy at
     // i'th checkpoint on street
     int currEnergy = 0 ;
  
     // flag to check if we have successfully 
     // crossed the street without any energy 
     // loss <= o at any checkpoint
     boolean flag = false ;
  
     // Traverse each check point lineraly
     for ( int i = 0 ; i < n; i++) {
     currEnergy += arr[i];
  
     // If current energy, becomes negative or 0, // increment initial minimum energy by the negative
     // value plus 1. to keep current energy
     // positive (at least 1). Also
     // update current energy and flag.
     if (currEnergy <= 0 ) {
         initMinEnergy += Math.abs(currEnergy) + 1 ;
         currEnergy = 1 ;
         flag = true ;
     }
     }
  
     // If energy never became negative or 0, then
     // return 1. Else return computed initMinEnergy
     return (flag == false ) ? 1 : initMinEnergy;
}
  
// Driver code
public static void main(String[] args)
{
     int arr[] = { 4 , - 10 , 4 , 4 , 4 };
     int n = arr.length;
     System.out.print(minInitialEnergy(arr, n));
}
}
  
// This code is contributed by Anant Agarwal.

python

# Python program to find mimimum initial enery to
# reach end
  
# Function to calculate minimum initial enery
# arr[] stroes enery at each checkpoints on street
def minInitialEnergy(arr):
     n = len (arr)
      
     # initMinEnergy is variable to store minimum initial
     # energy required
     initMinEnergy = 0 ;
      
     # currEnery is variable to store current value of
     # enery at i'th checkpoint on street
     currEnergy = 0 
  
     # flag to check if we have successfully crossed the
     # street without any energy loss <= 0 at any checkpoint 
     flag = 0 
      
     # Traverse each check point linearly
     for i in range (n):
         currEnergy + = arr[i]
          
         # If current energy, becomes negative or 0, increment
         # initial minimum energy by the negative value plus 1.
         # to keep current energy positive (at least 1). Also
         # update current energy and flag.
         if currEnergy < = 0 :
             initMinEnergy + = ( abs (currEnergy) + 1 )
             currEnergy = 1 
             flag = 1
  
     # If energy never became negative or 0, then 
     # return 1. Else return computed initMinEnergy
     return 1 if flag = = 0 else initMinEnergy
  
  
# Driver program to test above function
arr = [ 4 , - 10 , 4 , 4 , 4 ]
print minInitialEnergy(arr)
  
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to find minimum 
// C# program to find minimum 
// initial energy to reach end
using System;
  
class GFG {
      
// Function to calculate minimum 
// initial energy arr[] stores energy
// at each checkpoints on street
static int minInitialEnergy( int []arr, int n) 
{
      
     // initMinEnergy is variable to store 
     // minimum initial energy required.
     int initMinEnergy = 0;
  
     // currEnergy is variable to store 
     // current value of energy at
     // i'th checkpoint on street
     int currEnergy = 0;
  
     // flag to check if we have successfully 
     // crossed the street without any energy 
     // loss <= o at any checkpoint
     bool flag = false ;
  
     // Traverse each check point lineraly
     for ( int i = 0; i < n; i++) {
     currEnergy += arr[i];
  
     // If current energy, becomes negative or 0, // negativeincrement initial minimum energy 
     // by the value plus 1. to keep current 
     // energy positive (at least 1). Also
     // update current energy and flag.
     if (currEnergy <= 0)
     {
         initMinEnergy += Math.Abs(currEnergy) + 1;
         currEnergy = 1;
         flag = true ;
     }
     }
  
     // If energy never became negative
     // or 0, then return 1. Else return
     // computed initMinEnergy
     return (flag == false ) ? 1 : initMinEnergy;
}
  
// Driver code
public static void Main()
{
     int []arr = {4, -10, 4, 4, 4};
     int n = arr.Length;
     Console.Write(minInitialEnergy(arr, n));
}
}
  
// This code is contributed by Nitin Mittal.

的PHP

<?php
// PHP program to find minimum 
// initial energy to reach end
  
// Function to calculate minimum 
// initial energy arr[] stores 
// energy at each checkpoints on street
function minInitialEnergy( $arr , $n )
{
     // initMinEnergy is variable
     // to store minimum initial
     // energy required.
     $initMinEnergy = 0;
  
     // currEnergy is variable to
     // store current value of energy
     // at i'th checkpoint on street
     $currEnergy = 0;
  
     // flag to check if we have 
     // successfully crossed the 
     // street without any energy
     // loss <= o at any checkpoint
     $flag = 0;
  
     // Traverse each check
     // point lineraly
     for ( $i = 0; $i < $n ; $i ++)
     {
         $currEnergy += $arr [ $i ];
  
         // If current energy, becomes
         // negative or 0, increment
         // initial minimum energy by 
         // the negative value plus 1.
         // to keep current energy 
         // positive (at least 1). Also 
         // update current energy and flag.
         if ( $currEnergy <= 0)
         {
             $initMinEnergy += abs ( $currEnergy ) + 1;
             $currEnergy = 1;
             $flag = 1;
         }
     }
  
     // If energy never became 
     // negative or 0, then
     // return 1. Else return 
     // computed initMinEnergy
     return ( $flag == 0) ? 1 : $initMinEnergy ;
}
  
// Driver Code
$arr = array (4, -10, 4, 4, 4);
$n = sizeof( $arr );
echo minInitialEnergy( $arr , $n );
  
// This code is contributed 
// by nitin mittal. 
?>

输出：

7

时间复杂度：

上)

辅助空间：

O(1)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: