【蓝桥杯冲冲冲】排队接水--贪心算法巩固 (≧∇≦)-Toy模板网

这篇具有很好参考价值的文章主要介绍了【蓝桥杯冲冲冲】排队接水--贪心算法巩固 (≧∇≦)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

蓝桥杯备赛 | 洛谷做题打卡day15

排队接水

题目描述

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

输入格式

第一行为一个整数 $n$ 。

第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的接水时间 $T_i$ 。

输出格式

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

样例 #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\le n \leq 1000$ ， $1\le t_i \leq 10^6$ ，不保证 $t_i$ 不重复。

思路

有一个巧妙的存数据方式来输出排序之后编号的顺序

（针对快排懒得用结构体的同学）

因为n<=1000

所以给每个ti都*1001，在加上当前序号

可以保证排序的时候序号不干扰排序

又可以方便输出序号（只需mod1001输出序号，／1001 输出时间）

【蓝桥杯冲冲冲】排队接水--贪心算法巩固 (≧∇≦),蓝桥杯备赛,蓝桥杯,贪心算法,职场和发展

题解代码

学会利用新知，自己多试试并尝试积攒一些固定解答方案，debug，以下是题解代码 ~

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
double sum;
long int n;
long long int t[1001];
double ans;
int main(int argc, const char * argv[])
{
    cin>>n;
    int x;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        t[i]=x*1001+i;
    }
    sort(t+1,t+1+n);
    for(int j=1;j<=n;j++)
    {
        cout<<t[j]%1001<<" ";
        sum+=t[j]/1001*(n-j);
    }
    cout<<endl;
    ans=sum/n;
    printf("%0.2lf",ans);
    return 0;
}

我的一些话

今天继续巩固贪心算法，多思考思路还是很好掌握的，虽然一次性AC有一定难度，需要通盘的考虑和理解，以及扎实的数据结构基础才能独立写出AC代码。但无论难易，大家都要持续做题，保持题感喔！一起坚持(o´ω`o)
如果有非计算机专业的uu自学的话，关于数据结构的网课推荐看b站上青岛大学王卓老师的课，讲的很细致，有不懂都可以私信我喔
总结来说思路很重要，多想想，多在草稿纸上画画，用测试数据多调试，debug后成功编译并运行出正确结果真的会感到很幸福！
关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识，之前的博文我都有写，欢迎大家关注我，翻阅自取哦~
不管什么都要坚持吧，三天打鱼两天晒网无法形成肌肉记忆和做题思维，该思考的时候一定不要懈怠，今天就说这么多啦，欢迎评论留言，一起成长：）文章来源地址https://www.toymoban.com/news/detail-821768.html