贪心_接水问题

题目链接：贪心_接水问题

一. 算法思路

我们要让平均接水的时间更少，那么肯定让花费时间更少的人排在前面，所以我们要用sort(使用sort要包含算法头文件algorithm)去给接水时间排序，但是我们发现我们输出的时候是按照第几个人来输出的，也就是按照一开始的下标，所以我们的思路就是用一个结构体把第k个人和他节水所用的时间绑定在一起，然后把结构体放到一个数组里面，并且比较大小的时候是以接水时间为基准去比较的(直接给数组sort排序一下即可)

如何计算平均时间？
答：我们从第二个人开始算，因为第一个人不需要等待，第k个人等待的时长就是前面所有人的接水时间，我们用cur来表示第k个人等待的时长，我们用一个count记录所有人等待的总时长，最后用double类型的数接受平均数即可，输出保留两位小数建议用printf，因为更方便

二. 具体代码实现

#include<iostream>#include<algorithm>usingnamespacestd;structnode{booloperator<(structnode&b)const{return_b<b._b;}//_a是第k个人，_b是所用时长int_a,_b;};constintN=1010;node a[N];intmain(){intn;cin>>n;for(inti=1;i<=n;i++){intx;cin>>x;a[i]={i,x};}//排序输出下标sort(a+1,a+n+1);for(inti=1;i<=n;i++){cout<<a[i]._a<<" ";}cout<<endl;//计算时间intt=0;intcount=0;for(inti=2;i<=n;i++){t+=(a[i-1]._b);count+=t;}doublefin=(1.0)*count/n;printf("%.2lf",fin);return0;}