主要的思路是设到达最后一个时,能量消耗已经为0,接着依次逆序处理。由于中途存在向上取整的问题,所以计算出的最少能量在正序推时最后的能量不一定为0.
#include<iostream> #include<iomanip> #include<vector> #include<map> #include<string> #include<algorithm> using namespace std; int main(){ int n,h; cin >> n; vector<int> H; for(int i = 0;i < n;i++){ cin >>h; H.push_back(h); } int e = 0; int temp; for(int j = n - 1;j >= 0;j--){ //cout << "当前是第"<<j<<"个位置,此时的能量是"<< e <<"下一个H的高度为" << H[j+1]<< endl; temp = (e + H[j]) / 2; if(( e + H[j]) % 2 != 0){ temp += 1; } e = temp; } cout << e; return 0; }