道路を横断するために必要な最小初期エネルギー

GfG Practice で試してみる

#practiceLinkDiv { 表示: なし !重要; }

正の数値と負の数値を含む配列を指定します。配列は、通りの一方の端からもう一方の端までのチェックポイントを表します。正と負の値は、そのチェックポイントでのエネルギー量を表します。正の数はエネルギーを増加させ、負の数は減少します。エネルギーレベルが 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   
Recommended Practice  最小エネルギー    試してみてください!       ブルートフォースアプローチ:    
     考えられるすべての初期エネルギー レベル (1 から開始) について、そのエネルギー レベルを使用して道路の横断をシミュレートし、エネルギー レベルが常に正のままであるかどうかを確認します。  
  エネルギー レベルがゼロまたは負にならないようにする最小の初期エネルギー レベルを返します。  
 
 
  以下は上記のアプローチのコードです。  
 C++      #include       using     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  ;   }   
  Java      import     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 akshitaguprzj3   
  Python3      # 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 AGARWAL   
  C#      using     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  ));      }      }   }   
  JavaScript      // Function to check if energy level never becomes negative or zero   function     check  (  arr       n       initEnergy  )     {      let     energy     =     initEnergy  ;      for     (  let     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   function     minInitialEnergy  (  arr       n  )     {      let     minEnergy     =     1  ;      while     (  !  check  (  arr       n       minEnergy  ))     {      minEnergy  ++  ;      }      return     minEnergy  ;   }   // Driver code   let     arr     =     [  4       -  10       4       4       4  ];   let     n     =     arr  .  length  ;   console  .  log  (  minInitialEnergy  (  arr       n  ));   
       出力:    
   7   
     時間計算量 :    O(2^n)  
      補助スペース:    の上）  
   初期の最小エネルギー 0 を採用します。 initMinEnergy = 0、および任意のチェックポイントのエネルギーを currEnergy = 0 とします。次に、各チェックポイントを線形に走査し、各 i 番目のチェックポイントでエネルギー レベルを追加します。 currEnergy = currEnergy + arr[i]。 currEnergy が正でなくなった場合、この点を超えるには少なくとも 'abs(currEnergy) + 1' の追加の初期エネルギーが必要になります。したがって、initMinEnergy = (initMinEnergy + abs(currEnergy) + 1) を更新します。次のポイントに必要な追加の最小初期エネルギーが得られたため、currEnergy = 1 も更新します。  
   以下は上記のアイデアを実装したものです。   
 C++      // C++ program to find minimum initial energy to    // reach end    #include          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 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  ;      }      
  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 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.   
  Python3      # 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)   
  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 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.   
  JavaScript       <  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>   
  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 linearly   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(n)      
    補助スペース : O(1)