首页 > 代码库 > NOJ1076 机器狗组装费用 贪心
NOJ1076 机器狗组装费用 贪心
题目描述
sed同学最近迷上了制造机器狗,购置了大量所需零件,零件可以组装为一个组件,这些组件或零件又可以组装为一个大的组件。在制造机器狗中,组件或零件只能两两进行组装,组装的顺序任意。在机器狗中,每个零件都有一个组装成本,每次组装一个组件的费用为各个零件组装成本之和。给定各个零件组装成本(单位为元),你的任务是帮助sed计算他至少花费多少费用。
输入
第一行包括一个整数N,表示机器狗零件数(1≤N≤10000)
第二行为N个正整数,表示每个机器狗零件组装成本(单位为元),整数之间用空格隔开。
输出
输出仅一行,即机器狗组装的最少费用。
注意:输出部分的结尾要求包含一个多余的空行。
样例输入
10
1 2 3 4 5 6 7 8 9 0
样例输出
136
解题思路
题目抽象起来就是n个数字的两两合并 明显可以用贪心来解 只需要知道当前的最小的两个零件 把它们组合起来即可。O(n^2)搞定 详见代码
#include <cstdio> #include <algorithm> #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; }
NOJ1076 机器狗组装费用 贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。