【排序】紧急集合

问题 C: 【排序】紧急集合

时间限制: 1 Sec 内存限制: 64 MB
提交: 32 解决: 13
[提交] [状态] [讨论版] [命题人:]

题目描述

史上著名的大魔导师列别捷夫曾经说过：“平静的湖面，锻炼不出精悍的水手；安逸的生活打造不出时代的伟人。”这句话用在监狱的狱警身上实在是再恰当不过，由于监狱一千年来从未出过任何差错，因此几乎所有的狱警都或多或少的有些懒散，我们可以将之量化为一个数值即懒散值。所以当典狱长决定集合n个狱警以围捕修罗王和邪狼时，他所花费的体力是可观的。

典狱长一次可以将两群人集合在一起，所花费的体力是这两堆人的懒散值之和。可以看出，经过n－1次集合，所有的狱警就集合在一起了。例如有3个狱警，懒散值依次为1，2，9。可以先将懒散值为1、2的狱警合并为一群，新群数目为3，耗费体力为3。接着，将新群与懒散值为９的狱警合并，又得到新的群，数目为12，耗费体力为12。所以典狱长总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。那么，怎样集合，典狱长花费的体力最少呢？

输入

包括两行，第一行是一个整数n(1≤n≤10000)，表示狱警人数。第二行包含n个整数，用空格分隔，第i个整数a_i(1≤a_i≤20000)是第i个狱警的懒散值。

输出

包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2³¹。

样例输入

3
1 2 9

样例输出

提示

对于30％的数据，保证有n≤1000；
对于50％的数据，保证有n≤5000；
对于全部的数据，保证有n≤10000。

代码：

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#define range(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
#define rerange(i,a,b) for(int i=a;i>=b;--i)
#define fill(arr,tmp) memset(arr,tmp,sizeof(arr))
using namespace std;
int n;
vector<int>num(10005);
void init(){
    cin>>n;
    range(i,1,n)cin>>num[i];
    sort(num.begin()+1,num.begin()+1+n);
}
void solve(){
    LL ans=0;
    range(i,2,n){
        ans+=num[i-1]+num[i];
        num[i]+=num[i-1];
        sort(num.begin()+i,num.begin()+1+n);
    }
    cout<<ans<<endl;
}
int main() {
    init();
    solve();
    return 0;
}

View Code