csp信奥赛C++高频考点专项训练之贪心算法 --【排序贪心】：排队接水

csp信奥赛C高频考点专项训练之贪心算法 --【排序贪心】排队接水题目描述有n nn个人在一个水龙头前排队接水假如每个人接水的时间为T i T_iTi​请编程找出这n nn个人排队的一种顺序使得n nn个人的平均等待时间最小。输入格式第一行为一个整数n nn。第二行n nn个整数第i ii个整数T i T_iTi​表示第i ii个人的接水时间T i T_iTi​。输出格式输出文件有两行第一行为一种平均时间最短的排队顺序第二行为这种排列方案下的平均等待时间输出结果精确到小数点后两位。输入输出样例 1输入 110 56 12 1 99 1000 234 33 55 99 812输出 13 2 7 8 1 4 9 6 10 5 291.90说明/提示1 ≤ n ≤ 1000 1\le n \leq 10001≤n≤10001 ≤ t i ≤ 10 6 1\le t_i \leq 10^61≤ti​≤106不保证t i t_iti​不重复。思路分析关键点贪心策略按接水时间升序排列可确保总等待时间最小这是贪心算法的经典应用。时间复杂度双重循环计算总和的时间复杂度为O(n²)但n≤1000属于可接受范围。数值溢出处理使用long long类型存储总和避免大数相加时溢出。实现步骤结构体定义node结构体存储每个人的接水时间t和原始编号id便于排序后仍能追踪原始位置。排序策略使用贪心算法按接水时间从小到大排序。时间相同时按编号排序以确保输出顺序的唯一性。输出排队顺序排序后的结构体数组直接输出id即为最优排队顺序。计算总等待时间总等待时间为每个人等待时间的总和。第i个人排序后的等待时间等于前面i-1个人的接水时间之和。通过双重循环累加每个后续人员需要等待前面所有人员的时间总和即为总等待时间。平均时间计算总等待时间除以人数保留两位小数输出。代码实现#includebits/stdc.husingnamespacestd;intn;// 定义结构体存储每个人的接水时间和原始编号structnode{intt;// 接水时间intid;// 原始编号}a[1010];// 排序比较函数优先按接水时间从小到大排序时间相同则按编号从小到大排序boolcmp(node a,node b){if(a.t!b.t)returna.tb.t;elsereturna.idb.id;}intmain(){cinn;// 输入数据并初始化结构体数组for(inti1;in;i){cina[i].t;a[i].idi;// 记录原始编号}// 按照贪心策略排序使得总等待时间最小sort(a1,an1,cmp);// 注意数组从1开始// 输出最优排队顺序for(inti1;in;i){couta[i].id ;}coutendl;// 计算总等待时间longlongsum0;// 对于第i个人排序后的他前面有i-1个人他们的接水时间都会累加到他的等待时间中for(inti2;in;i){// 从第二个人开始计算等待时间for(intj1;ji-1;j){// 累加前面所有人的接水时间suma[j].t;}}// 计算平均等待时间并输出保留两位小数doubleavgsum*1.0/n;coutfixedsetprecision(2)avg;return0;}各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}