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

输入 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

说明/提示

1 ≤ n ≤ 1000 1\le n \leq 10001≤n≤1000，1 ≤ t i ≤ 10 6 1\le t_i \leq 10^61≤ti​≤106，不保证t i t_iti​不重复。

思路分析

关键点

• 贪心策略：按接水时间升序排列可确保总等待时间最小，这是贪心算法的经典应用。
• 时间复杂度：双重循环计算总和的时间复杂度为O(n²)，但n≤1000，属于可接受范围。
• 数值溢出处理：使用long long类型存储总和，避免大数相加时溢出。

实现步骤

1. 结构体定义：node结构体存储每个人的接水时间t和原始编号id，便于排序后仍能追踪原始位置。
2. 排序策略：使用贪心算法，按接水时间从小到大排序。时间相同时，按编号排序以确保输出顺序的唯一性。
3. 输出排队顺序：排序后的结构体数组直接输出id，即为最优排队顺序。
4. 计算总等待时间：
   • 总等待时间为每个人等待时间的总和。第i个人（排序后）的等待时间等于前面i-1个人的接水时间之和。
   • 通过双重循环累加每个后续人员需要等待前面所有人员的时间，总和即为总等待时间。
5. 平均时间计算：总等待时间除以人数，保留两位小数输出。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn;// 定义结构体，存储每个人的接水时间和原始编号structnode{intt;// 接水时间intid;// 原始编号}a[1010];// 排序比较函数：优先按接水时间从小到大排序，时间相同则按编号从小到大排序boolcmp(node a,node b){if(a.t!=b.t)returna.t<b.t;elsereturna.id<b.id;}intmain(){cin>>n;// 输入数据并初始化结构体数组for(inti=1;i<=n;i++){cin>>a[i].t;a[i].id=i;// 记录原始编号}// 按照贪心策略排序，使得总等待时间最小sort(a+1,a+n+1,cmp);// 注意数组从1开始// 输出最优排队顺序for(inti=1;i<=n;i++){cout<<a[i].id<<" ";}cout<<endl;// 计算总等待时间longlongsum=0;// 对于第i个人（排序后的），他前面有i-1个人，他们的接水时间都会累加到他的等待时间中for(inti=2;i<=n;i++){// 从第二个人开始计算等待时间for(intj=1;j<=i-1;j++){// 累加前面所有人的接水时间sum+=a[j].t;}}// 计算平均等待时间并输出，保留两位小数doubleavg=sum*1.0/n;cout<<fixed<<setprecision(2)<<avg;return0;}

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;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++标准模板库STL：
https://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 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}