题目描述

贪心，合并次数是不能改变的，每次都尽可能选择合并花费少的。

sort一下，从小到大合并即可。

算法1

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=1e5+10;

LL ans=0;
LL a[N];
int n;

int main()
{
    scanf("%d",&n);

    for(int i=0;i<n;i++) scanf("%lld",&a[i]);

    sort(a,a+n);

    int sum=a[0];

    for(int i=1;i<n;i++)
    {
        ans += sum*a[i]; 
        sum += a[i];
    }

    cout<<ans<<endl;

    return 0;
}