双十一吃土

吃土

时间限制: 1000 ms 内存限制: 65536 kb

总通过人数: 132 总提交人数: 133

题目描述

输入

多组测试数据（不超过10组），每组数据两行

第一行为一个正整数N（N<=10000），表示排队挖土的总人数

第二行为N个正整数a1,a2,,,an（INT范围内），表示每个人挖土所需的时间

输出

对于每组数据，输出一行，表示等待时间之和的最小值

输入样例

5
1 2 3 4 5

输出样例

20

题目来源：http://biancheng.love/contest/17/problem/A/index

解题分析：
按照题目定义，当挖土的时间排序为a1,a2,....an,时，所消耗的时间为T= ∑（i=1->n）（n-i）*ai; 因此当所消耗时间最少时，挖图时间的排序序列应改为非递减排序。因此可以调用库函数的sort，也可以使用前些天提到的优先队列。
代码实现：

#include <bits/stdc++.h>
#define max_size 10010
long long a[max_size];
using namespace std;

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        long long ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=(n-i)*a[i];
        }
        printf("%lld
",ans);
    }
}

另附优先队列实现：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        long long num;
        priority_queue<long long,vector<long long>,greater<long long> >que;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&num);
            que.push(num);
        }
        long long kase=1;
        long long ans=0;
        while(!que.empty())
        {
            ans+=(n-kase)*que.top();
            que.pop();
            kase++;
        }
        printf("%lld
",ans);
    }
}

注意事项：计算结果较大请使用long long 数据类型。