解题思路

这是一个动态规划的反向推导问题。需要从终点向起点计算每个位置所需的最小能量。

关键点:

  1. 从后向前计算最小能量
  2. 考虑能量转换规则
  3. 处理向上取整的情况
  4. 保证每步能量都为正

算法步骤:

  1. 从最后一个建筑开始
  2. 计算每个位置所需的最小能量
  3. 返回起点所需能量

代码

#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))

算法及复杂度

  • 算法:动态规划(反向推导)
  • 时间复杂度:,只需遍历一次数组
  • 空间复杂度:,只需要常数级额外空间