【贪心】排队接水

<center>

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

时间限制: 1 Sec  内存限制: 128 MB
提交: 38  解决: 20
[提交][状态][讨论版]
</center>

题目描述

有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 <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef struct node{
    int t;
    int cou;
};
node a[1000];

int cmp(node a,node b){
    return a.t<b.t;
}

int main()
{
    int n;
    int every=0;
    double avg;
    int sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i].t);
        a[i].cou=i+1;
    }
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++){
        if(i==n-1){
            printf("%d\n",a[i].cou);
        }else{
            printf("%d ",a[i].cou);
        }

        if(i!=0){
            every+=a[i-1].t;
        }
        sum+=every;
    }
    avg=sum*1.0/n;
    printf("%.2f",avg);
    return 0;
}

 

 
全部评论

相关推荐

06-19 19:06
门头沟学院 Java
码农索隆:别去东软,真学不到东西,真事
点赞 评论 收藏
分享
05-16 11:16
已编辑
东华理工大学 Java
牛客73769814...:盲猜几十人小公司,庙小妖风大,咋不叫她去4️⃣呢😁
牛客创作赏金赛
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 18:02
好不容易拿到了字节Offer,鼠鼠做后端的,但家里人觉得可能被裁员不稳定,让鼠鼠去投国企,现在好纠结到底该咋选
文档传偷助手:该投就投吧,不过建议别放弃offer 拿到手里的才是最好的
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务