20.排队接水

前言

意外地更新一下ヾ(≧▽≦*)o
以后可能会有不定期更新,感谢大家支持🤞

---

作者：xyzlh

---

今天来看一条比较基础的贪心题
洛谷传送门:排队接水

题目

题目描述

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

输入格式

第一行为一个整数n
第二行n个整数，第i个整数T$_i$表示第i个人的等待时间T$_i$。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

输入输出样例

输入#1
10
56 12 1 99 1000 234 33 55 99 812
输出#1
3 2 7 8 1 4 9 6 10 5
291.90

说明/提示

n≤1000,t$_i$≤$10^6$,不保证 $t_i$不重复。
当$t_i$重复时，按照输入顺序即可（sort 是可以的）

思路分析

看到这条题目我们会想到用贪心去解决，因为要使等待时间最少，
就要尽可能地让接水时间短的人排在前面。这样后面的人等待的时间
就少。
证明
假设有n个人接水，每个人时间为$t_1$,$t_2$,$t_3$,……$t_n$
接水总时间就为$t_1(n-1)$+$t_2(n-2)$+…+$t_n$
想要让接水总时间最短，就要让$t_1<t_2<t_3<…<t_n$

还有一个问题就是在累加时间时，假如算出每个人的等待时间会比较麻烦，
所以我们可以推导一下表达式：
第一个人接水，后面2到n人需要等待时间为t[1](n-1)
第二个人接水，后面3到n人需要等待时间为t[2](n-2)
所以就得到了这样的一个表达式：$t$=$t_1(n-1)$+$t_2(n-2)$+…+$t_n$

代码

直接上代码

#include<bits/stdc++.h>
using namespace std;
int t[1001],a[1001];
int main(){
    int n;
    long long total=0;//计数器归零
    double ans;
    cin>>n;
    for(int i=1;i<=n;i++){//输入数据
        cin>>t[i];
        a[i]=i;
    }
    for(int i=1;i<n;i++){//手写一个冒泡，其实也可以用sort
        for(int j=1;j<=n-i;j++){
            if(t[j]>t[j+1]){
                swap(t[j],t[j+1]);
                swap(a[j],a[j+1]);
            }
        }
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++){//累加
        total+=t[i]*(n-i);
    }
    cout<<fixed<<setprecision(2)<<total/(n*1.0);//最后记得保留2位小数
    return 0;
} 

如果您有更好的思路或者其他语言的代码，欢迎您在评论区中提出😁

这期到这里就结束了，我们下期再见！😊

本文作者： 益题 Yitee
发布时间： 2021-08-24
最后更新： 2021-08-24
本文标题： 20.排队接水
本文链接： https://yitee.top/posts/25175.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！

赏

谢谢你请我吃糖果

微信