问题 A: 【贪心】排队接水

问题 A: 【贪心】排队接水

时间限制: 1 Sec  内存限制: 128 MB
[命题人:外部导入]

题目描述

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

输入

共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。

输出

有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

样例输入

10

56 12 1 99 1000 234 33 55 99 812

样例输出

3 2 7 8 1 4 9 6 10 5

291.90

#include<cstdio>

#include <map>

#include<iostream>

#include<string>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

inline int read() {int x=,f=;char c=getchar();while(c!='-'&&(c<''||c>''))c=getchar();if(c=='-')f=-,c=getchar();while(c>=''&&c<='')x=x*+c-'',c=getchar();return f*x;}

typedef long long ll;

const int maxn=5e5+;

struct node{

    int flag;

    int time;

}a[maxn];

bool cmp(node x,node y){

    return x.time<y.time;

}

int main(){

    int n;

    cin>>n;

    for(int i=;i<=n;i++){

        cin>>a[i].time;

        a[i].flag=i;

    }

    sort(a+,a+n+,cmp);

    for(int i=;i<n;i++){

        printf("%d ",a[i].flag);//小的先接水

    }

    printf("%d\n",a[n].flag);

    double sum=;

    for(int i=;i<=n;i++){

        sum+=(n-i)*a[i].time;

    }

    printf("%.2lf",sum*1.0/);

}