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

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

## 本文概述

``````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``````

## 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);
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) 