算法题每日一练---第30天：部落谈判

一、问题描述

在很久很久以前，有 n 个部落居住在平原上，依次编号为 1 到 n。第 i个部落的人数为 ti。

有一年发生了灾荒。年轻的政治家小蓝想要说服所有部落一同应对灾荒，他能通过谈判来说服部落进行联合。

每次谈判，小蓝只能邀请两个部落参加，花费的金币数量为两个部落的人数之和，谈判的效果是两个部落联合成一个部落（人数为原来两个部落的人数之和）。

二、题目要求

输入描述

输入的第一行包含一个整数 n，表示部落的数量。

第二行包含 n 个正整数，依次表示每个部落的人数。

其中，1≤n≤1000，1≤ti≤10^4。

输出描述

输出一个整数，表示最小花费。

测试数据

输入4个数字分别为9 1 3 5，输出结果为31

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

三、问题分析

这是一道考察贪心最优解的问题，题目要求将n个部落聚合到一起，使之花费最少，那我们每一次谈判都邀请人数最少的两个部落不就行了。

以测试数据为例，先进行一次排序：135913合在一起变成4，4重新加入后排序45945合在一起变成9，重新加入后排序99最后，所有结果相加：4+9+9+9=31

排序可以使用C++中的排序函数，不需要自己编写，那两个数字相加重新加入的数字怎么办？

第一步1 3合并成4，我们可以让4赋值给3，1变成0，那么数组的大小没变，排序也不受影响。

13合在一起变成4，4重新加入后排序045945合在一起变成9，重新加入后排序0099最后，所有结果相加：4+9+9+9=31

拓展

C++头文件algorithm中的sort函数：

以数组为例a[4]={3,4,1,2} , sort(a,a+4) 输 出 1 2 3 4

四、编码实现

#include<iostream>#include<algorithm>usingnamespacestd;
longlonginta[10008],sum=0;//初始化定义，应该不会超范围intmain()
{
inti,n;
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);//初始化排序for(i=0;i<n-1;i++)
    {
intmin=a[i]+a[i+1];//定义min存储数组内最小的两个元素a[i]=0;
a[i+1]=min;//第二个元素为minsum+=min;
sort(a,a+n);
    }
cout<<sum;//输出结果return0;
}