解题思路
这是一个动态规划的反向推导问题。需要从终点向起点计算每个位置所需的最小能量。
关键点:
- 从后向前计算最小能量
- 考虑能量转换规则
- 处理向上取整的情况
- 保证每步能量都为正
算法步骤:
- 从最后一个建筑开始
- 计算每个位置所需的最小能量
- 返回起点所需能量
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<int>& heights) {
int n = heights.size();
int min_energy = 0;
// 从后向前计算最小能量
for (int i = n - 1; i >= 0; i--) {
// 更新所需最小能量
min_energy = (min_energy + heights[i] + 1) / 2;
}
return min_energy;
}
};
int main() {
int n;
cin >> n;
vector<int> heights(n);
for (int i = 0; i < n; i++) {
cin >> heights[i];
}
Solution solution;
cout << solution.solve(heights) << endl;
return 0;
}
import java.util.*;
public class Main {
static class Solution {
public int solve(int[] heights) {
int n = heights.length;
int minEnergy = 0;
// 从后向前计算最小能量
for (int i = n - 1; i >= 0; i--) {
// 更新所需最小能量
minEnergy = (minEnergy + heights[i] + 1) / 2;
}
return minEnergy;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] heights = new int[n];
for (int i = 0; i < n; i++) {
heights[i] = sc.nextInt();
}
Solution solution = new Solution();
System.out.println(solution.solve(heights));
sc.close();
}
}
class Solution:
def solve(self, heights):
n = len(heights)
min_energy = 0
# 从后向前计算最小能量
for i in range(n - 1, -1, -1):
# 更新所需最小能量
min_energy = (min_energy + heights[i] + 1) // 2
return min_energy
# 读取输入
n = int(input())
heights = list(map(int, input().split()))
solution = Solution()
print(solution.solve(heights))
算法及复杂度
- 算法:动态规划(反向推导)
- 时间复杂度:,只需遍历一次数组
- 空间复杂度:,只需要常数级额外空间