Minimali pradinė energija, reikalinga norint kirsti gatvę
Išbandykite GfG praktikoje 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Duotas masyvas, kuriame yra teigiami ir neigiami skaičiai. Masyvas vaizduoja kontrolinius taškus nuo vieno iki kito gatvės galo. Teigiamos ir neigiamos reikšmės parodo energijos kiekį tame kontroline taške. Teigiami skaičiai padidina energiją, o neigiami skaičiai mažėja. Raskite mažiausią pradinę energiją, reikalingą norint pereiti gatvę, kad energijos lygis niekada netaptų 0 arba mažesnis nei 0.
Pastaba: Minimalios pradinės energijos vertė bus 1, net jei sėkmingai kirsime gatvę neprarasdami energijos iki mažesnės ir lygios 0 bet kuriame kontrolės taške. 1 reikalingas pradiniam patikrinimo taškui.
Pavyzdžiai:
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
Recommended Practice Minimali energija Išbandykite!Brutalios jėgos metodas:
- Kiekvienam galimam pradiniam energijos lygiui (pradedant nuo 1) imituokite gatvės kirtimą naudodami tą energijos lygį ir patikrinkite, ar energijos lygis visą laiką išlieka teigiamas.
- Grąžinkite minimalų pradinį energijos lygį, kuris užtikrina, kad energijos lygis niekada netaptų nuliu arba neigiamas.
Žemiau pateikiamas aukščiau pateikto metodo kodas:
C++Java#includeusing namespace std ; // Function to check if energy level never becomes negative or zero bool check ( int arr [] int n int initEnergy ) { int energy = initEnergy ; for ( int i = 0 ; i < n ; i ++ ) { energy += arr [ i ]; if ( energy <= 0 ) { return false ; } } return true ; } // Function to calculate minimum initial energy // arr[] stores energy at each checkpoints on street int minInitialEnergy ( int arr [] int n ) { int minEnergy = 1 ; while ( ! check ( arr n minEnergy )) { minEnergy ++ ; } return minEnergy ; } // Driver code int main () { int arr [] = { 4 -10 4 4 4 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); cout < < minInitialEnergy ( arr n ); return 0 ; } Python3import java.util.* ; public class GFG { // Function to check if energy level never becomes // negative or zero static boolean check ( int [] arr int n int initEnergy ) { int energy = initEnergy ; for ( int i = 0 ; i < n ; i ++ ) { energy += arr [ i ] ; if ( energy <= 0 ) { return false ; } } return true ; } // Function to calculate minimum initial energy // arr[] stores energy at each checkpoints on the street static int minInitialEnergy ( int [] arr int n ) { int minEnergy = 1 ; while ( ! check ( arr n minEnergy )) { minEnergy ++ ; } return minEnergy ; } // Driver code public static void main ( String [] args ) { int [] arr = { 4 - 10 4 4 4 }; int n = arr . length ; System . out . println ( minInitialEnergy ( arr n )); } } // This code is contributed by akshitaguprzj3C## Function to check if energy level never becomes negative or zero def check ( arr n initEnergy ): energy = initEnergy for i in range ( n ): energy += arr [ i ] if energy <= 0 : return False return True # Function to calculate minimum initial energy # arr stores energy at each checkpoints on street def minInitialEnergy ( arr n ): minEnergy = 1 while not check ( arr n minEnergy ): minEnergy += 1 return minEnergy # Driver code arr = [ 4 - 10 4 4 4 ] n = len ( arr ) print ( minInitialEnergy ( arr n )) # THIS CODE IS CONTRIBUTED BY CHANDAN AGARWALJavaScriptusing System ; namespace EnergyCheck { class GFG { // Function to check if energy level never becomes negative or zero static bool Check ( int [] arr int n int initEnergy ) { int energy = initEnergy ; for ( int i = 0 ; i < n ; i ++ ) { energy += arr [ i ]; if ( energy <= 0 ) { return false ; } } return true ; } // Function to calculate minimum initial energy // arr[] stores energy at each checkpoints on street static int MinInitialEnergy ( int [] arr int n ) { int minEnergy = 1 ; while ( ! Check ( arr n minEnergy )) { minEnergy ++ ; } return minEnergy ; } // Driver code static void Main ( string [] args ) { int [] arr = { 4 - 10 4 4 4 }; int n = arr . Length ; Console . WriteLine ( MinInitialEnergy ( arr n )); } } }Išvestis:
7
Laiko sudėtingumas: O(2^n)
Pagalbinė erdvė: O(n)
Imame pradinę minimalią energiją 0 t.y.; initMinEnergy = 0, o energija bet kuriame kontroliniame taške kaip currEnergy = 0. Dabar kiekvieną kontrolinį tašką eikite tiesiškai ir pridėkite energijos lygį kiekviename i-ajame taške, t.y.; currEnergy = currEnergy + arr[i]. Jei currEnergy tampa neteigiama, mums reikia bent „abs(currEnergy) + 1“ papildomos pradinės energijos, kad peržengtume šį tašką. Todėl atnaujiname initMinEnergy = (initMinEnergy + abs(currEnergy) + 1). Taip pat atnaujiname currEnergy = 1, nes dabar turime reikiamą papildomą minimalią pradinę energiją kitam taškui.
Žemiau yra aukščiau pateiktos idėjos įgyvendinimas.
C++Java// C++ program to find minimum initial energy to // reach end #includeusing 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 linearly 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 ; } Python3// 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 linearly 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.C## Python program to find minimum initial energy to # reach end # Function to calculate minimum initial energy # arr[] stores energy at each checkpoints on street def minInitialEnergy ( arr ): n = len ( arr ) # 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 <= 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)JavaScript// 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 linearly 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< script > // Javascript 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. let initMinEnergy = 0 ; // currEnergy is variable to // store current value of energy // at i'th checkpoint on street let currEnergy = 0 ; // flag to check if we have // successfully crossed the // street without any energy // loss <= o at any checkpoint let flag = 0 ; // Traverse each check // point linearly for ( let 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 = 1 ; } } // If energy never became // negative or 0 then // return 1. Else return // computed initMinEnergy return ( flag == 0 ) ? 1 : initMinEnergy ; } // Driver Code let arr = new Array ( 4 - 10 4 4 4 ); let n = arr . length ; document . write ( minInitialEnergy ( arr n )); // This code is contributed // by Saurabh Jaiswal < /script>
Išvestis7Laiko sudėtingumas: O(n)
Pagalbinė erdvė: O(1)
