解题思路:
只有保证每次搬运的是当前所有堆中重量最小的两堆果子才能使体力消耗最小;
使用set容器自动排序,但又考虑到重量肯能出现相同情况,就使用multiset(可以放入重复元素并自动排序)
参考代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e4 + 10; multiset<ll> st; int n; ll ans = 0; void solve(){//数据初始化 cin>>n; for(int i = 0;i<n;i++){ int m; cin>>m; st.insert(m);//加入会自动排序 } while(st.size()!=1){ ll temp = 0; auto it = st.begin();//it指向最小重量的那一堆 auto it2 = it; temp += *it;//加上最小堆这部分体积 it++;//it后移指向次小重量的那堆 st.erase(it2);//移除已经计算的最小堆 temp += *it;//加上次小堆这部分体积 st.erase(it);//移除已经计算的次小堆 st.insert(temp);//移除已经计算的次小堆 ans += temp;//temp就是这次搬运的体力消费 } cout<<ans; } int main(){ solve(); return 0; }
0.0分
2 人评分