题目描述
sed同学最近迷上了制造机器狗，购置了大量所需零件，零件可以组装为一个组件，这些组件或零件又可以组装为一个大的组件。在制造机器狗中，组件或零件只能两两进行组装，组装的顺序任意。在机器狗中，每个零件都有一个组装成本，每次组装一个组件的费用为各个零件组装成本之和。给定各个零件组装成本（单位为元），你的任务是帮助sed计算他至少花费多少费用。
输入
第一行包括一个整数N，表示机器狗零件数(1≤N≤10000)
第二行为N个正整数，表示每个机器狗零件组装成本（单位为元），整数之间用空格隔开。
输出
输出仅一行，即机器狗组装的最少费用。
注意：输出部分的结尾要求包含一个多余的空行。
样例输入
10
1 2 3 4 5 6 7 8 9 0
样例输出
136
解题思路
题目抽象起来就是n个数字的两两合并 明显可以用贪心来解 只需要知道当前的最小的两个零件 把它们组合起来即可。O(n^2)搞定 详见代码
#include#include #define ll long long #define INF 1000000010 using namespace std; const int maxn = 10010; int s[maxn]; int main() { int n; scanf("%d",&n); for(int i = 0 ; i < n ; i ++) scanf("%d",&s[i]); ll sum = 0; if(n == 1) { printf("%d\n",s[0]); }else { //????n-1?? int t = n-1; while(t--) { //??s?????????????????? int pt1,pt2; int _min = INF; for(int i = 0; i < n ; i ++) { if(_min > s[i]) { pt1 = i; _min = s[i]; } } _min = INF; for(int i = 0 ; i < n ; i ++) { if(_min > s[i] && i != pt1) { pt2 = i; _min = s[i]; } } sum += s[pt1] + s[pt2]; s[pt1] = s[pt1] + s[pt2]; s[pt2] = INF; } printf("%lld\n",sum); } return 0; }