洛谷 1223_排队接水_贪心

发布于 2019-05-03  829 次阅读


题目描述

有n个人在一个水龙头前排队接水,假如每个人接水的时间为Ti,请编程找出这n个人排队的一种顺序,使得n个人的平均等待时间最小。


思路

将全部从小到大排序了以后就是了。统计时间时要将前面的时间也算上
要long long
O(nlogn)


#include <stdio.h>
#include <algorithm>
using namespace std;
struct arr
{
    long long w,l;
}a[100000];
int cam(arr a,arr b)
{
    return a.w<b.w;
}
int main()
{
    long long n;
    scanf("%lld",&n);
    for (long long i=1;i<=n;i++)
    {
        scanf("%lld",&a[i].w);
        a[i].l=i;
    }
    sort(a+1,a+n+1,cam);
    long long s=0,t=0;
    for (long long i=1;i<=n;i++)
    {
        printf("%d ",a[i].l);
        s+=a[i].w*(n-i);
    }
    double ans=(s*1.0)/n;
    printf("\n%.2lf\n",ans);
}