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;}
如果觉得《贪心算法之最少体力消耗》对你有帮助,请点赞、收藏,并留下你的观点哦!