Description
小K没事干，他要搬砖头，为了达到较好的减肥效果，教练规定的方式很特别：
每一次，小K可以把两堆砖头合并到一起，消耗的体力等于两堆砖头的重量之和。
经过 n-1次合并后， 就只剩下一堆了。小K在搬砖头时总共消耗的体力等于每次合并所耗体力之和。小K为了偷懒，希望耗费的体力最小。
例如有 3堆砖头，数目依次为 1、2、9 。可以先将 1 、 2 堆合并，新堆数目为3 ，耗费体力为 3 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为12 。所以总共耗费体力 =3+12=15。可以证明 15为最小的体力耗费值。
Input
共两行。
第一行是一个整数 n(1≤n≤1000) ，表示砖头堆数。
第二行n个整数，每个整数表示每堆砖头的砖头块数。
Output
一个整数，也就是最小的体力耗费值。
Sample Input
3
1 2 9
Sample Output
15
算法思想
要使得消耗体力最少，只要每次搬的两堆砖是最轻的两堆即可将砖块按重量从小到大排序，从左往右搬每搬一次都可能会导致顺序的改变，如果每搬一次都重新排序，时间复杂度过大每次合并两堆砖块后，与右边的砖块比较，把重量比它轻的都向前移一步#include<iostream>#include<algorithm>using namespace std;int n; // 砖块堆数 int a[1010] = {0}; // 每堆砖块数目 int main(){cin >> n; for(int i=0; i<n; i++)cin >> a[i];int cost = 0; // 体力消耗sort(a, a+n);for(int i=0; i<n-1; i++){int cost_i = a[i] + a[i+1];int k = i+2;// 后面有比堆积的砖块少的向前移一位 while(a[k]<cost_i && k<n){a[k-1] = a[k];k++;}a[k-1] = cost_i;cost += cost_i; } cout << cost << endl;return 0;}
如果觉得《贪心算法之最少体力消耗》对你有帮助，请点赞、收藏，并留下你的观点哦！
