洛谷P1334瑞瑞的木板题解

我做这道题的原因

某位网友

暗恋一位叫瑞瑞的女生

于是我下决心AC了这道题

[手动滑稽]

题目描述

题目背景

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

题目描述

他测量栅栏并发现他需要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

思路

大体思路分析

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

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

排序后：
| 5 | 8 | 8 |
| ————– | —- | —- |

下面开始组合。

---

按先小后大的顺序进行组合：
| 13 | 8 |
| ————— | —- |

此时耗费能量=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;
}