洛谷题目链接

题目描述

题目背景

瑞瑞想要亲自修复在他的一个小牧场周围的围栏。

题目描述

他测量栅栏并发现他需要n根木板，每根的长度为整数l[i]。于是，他买了一根足够长的木板，长度为所需的n根木板的长度的总和，他决定将这根木板切成所需的n根木板（瑞瑞在切割木板时不会产生木屑，不需考虑切割时损耗的长度)。 瑞瑞切割木板时使用的是一种特殊的方式，这种方式在将一根长度为 xx 的木板切为两根时，需要消耗x个单位的能量。瑞瑞拥有无尽的能量，但现在提倡节约能量，所以作为榜样，他决定尽可能节约能量。显然，总共需要切割(n-1)次，问题是，每次应该怎么切呢？请编程计算最少需要消耗的能量总和。

输入格式

输入的第一行是整数，表示所需木板的数量n。 第2行到第(n+1)行，每行一个整数，第(i+1)行的整数l[i]代表第i根木板的长度l[i]。

输出格式

一个整数，表示最少需要消耗的能量总和。

输入输出样例

输入#1 3 8 5 8 输出#1 34

思路

大体思路分析

这道题和合并果子很类似。可以反着想，把几截木板组合成一整块木板。 先用样例来分析

858

如果刚开始就把大数放到一起，以后每次都会累加。所以先进行排序，把按照先小后大的顺序进行组合。

排序后：

588

下面开始组合。

---

按先小后大的顺序进行组合：

138

此时耗费能量=13

---

再次组合：

21

此时耗费能量=13+13+8=34

向代码转换

此样例只有3个数，存在特殊情况。最好用更多的数据进行分析。这里用2 1 9 4 每次组合所耗费能量=组合后的木板长度

那就可以先对数据进行排序，选取最小的2个进行组合，再排序，再组合……

完整代码

#include<iostream> #include<algorithm> using namespace std; bool cmp(long long a,long long b){ //大到小排序 return a>b; } int main(){ int n; long long l[25000],ans=0; //木板长度，答案 cin>>n; for(int i=0;i<n;i++){ cin>>l[i]; } sort(l,l+n,cmp);//先排序 for(int i=n-1,a=0;i>0;i--,a++){ l[i-1]+=l[i]; ans+=l[i-1]; int j=i-1; while(l[j]>l[j-1] && j>0){ swap(l[j],l[j-1]); j--; } } cout<<ans; return 0; }