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

蓝桥杯备赛 | 洛谷做题打卡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\le 1000$，$1\le t_i\le 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后成功编译并运行出正确结果真的会感到很幸福！

• 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识，之前的博文我都有写，欢迎大家关注我，翻阅自取哦~

• 不管什么都要坚持吧，三天打鱼两天晒网无法形成肌肉记忆和做题思维，该思考的时候一定不要懈怠，今天就说这么多啦，欢迎评论留言，一起成长：）