資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時尚研究
法律研究C++ 中穿過街道所需的最低初始能量
假設我們有一個數組，其中儲存了正負數。該陣列表示從一條街道的一端到另一端的檢查點。正負數表示檢查點的能量。正值可增加能量，負值可減少能量。我們必須找到穿越街道所需的初始能量級，這樣能量級永遠不會變為 0 或低於 0。
假設我們有一個數組 A = {4, -6, 2, 3}。將初始能量設為 0。因此，到達第一個檢查點後，能量為 4。現在，要到達第二個檢查點，能量將為 4 + (-6) = -2。因此能量小於 0。因此我們必須以 3 開始旅程。第一項之後，它將變為 3 + 4 = 7，到達第二個檢查點之後，它將變為 7 + (-6) = 1。
演算法
minInitEnergy(arr, n): begin initEnergy := 0 currEnergy := 0 flag := false for i in range 0 to n, do currEnergy := currEnergy + arr[i] if currEnergy <= 0, then initEnergy := initEnergy + absolute value of currEnergy + 1 currEnergy := 1 flag := true end if done if flag is false, return 1, otherwise return initEnergy end
範例
#include <iostream>
#include <cmath>
using namespace std;
int minInitEnergy(int arr[], int n){
int initEnergy = 0;
int currEnergy = 0;
bool flag = false;
for (int i = 0; i<n; i++){
currEnergy = currEnergy + arr[i];
if (currEnergy <= 0){
initEnergy = initEnergy + abs(currEnergy) + 1;
currEnergy = 1;
flag = true;
}
}
if (flag == false)
return 1;
else
return initEnergy;
}
int main() {
int A[] = {4, -6, 2, 3};
int n = sizeof(A)/sizeof(A[0]);
cout << "Minimum Energy: " << minInitEnergy(A, n);
}輸出
Minimum Energy: 3
更新於:2019 年 9 月 25 日
373 次瀏覽
廣告