数据结构
网络
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 次浏览
广告