牛客题库快排算法：小杰的签到题
在牛客刷算法题的时候遇到这个题目，发现CSDN中找到的题解都比较繁琐不方便阅读，所以今天写了一个相对简洁的题解
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
小杰组织了一场比赛，在比赛前需要安排队伍签到，但他不确定签到要花多久时间，现在他来请求你的帮助。已知签到是在一个体育馆，该体育馆布置有三个桌子以供不同队伍的队伍同时签到，一个桌子最多只能有一支队伍签到，一支队伍只需在一张桌子前完成签到即可。如果三个桌子都有队伍在签到，其它需要签到的队伍就需要在任意一个桌子前排队，等待签到。
我们假设在t=0的时刻开始接受签到，n支队伍分别在a1,a2,...,an时刻到达体育馆，每支队伍完成签到均需b的时间，为使问题简单，我们忽略体育馆中移动的时间。你需要告诉小杰最早什么时刻，所有的队伍均签到完成。
输入描述:
多组读入。
输入数据的第一行是一个整数T，表示数据的组数。
每组数据的第一行是一个整数n，表示签到的队伍数。
接下来一行有n个整数ai，表示第i支队抵达体育馆的时间。
每组的最后一行是一个整数b，表示一支队伍完成签到的时间。
输出描述:
对于每组数据，输出最后一支队伍最早签到完成的时刻。
输入：
2
5
1 2 4 5 7
4
7
4 4 4 2 8 9 11
5
预测输出：
11
17
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010;
int n,b,T;
int q[N],tme[3];//c++中全局变量会自动赋值为零
int main(void)
{
cin >> T;
//对T组数据循环处理
while(T --)
{
cin >> n;//读入数组长度即队伍数量
for(int i = 0; i < n; i ++)cin >> q[i];//循环读入数组各个元素，即各队到达的时刻
cin >> b;//读入每队签到所需时间
sort(q,q+n);//为方便书写这里用<algorithm>头文件中的sort函数来代替快排对数组q进行排序
//快排会比sort快一些但在数据量较小的情况下两者相差无几
for(int i = 0;i < 3; i ++)tme[i] = 0;//每次循环都要让tme数组归零
for(int i = 0;i < n; i ++)
{
sort(tme,tme+3);//将tme数组从小到大排序
if(tme[0] < q[i]) tme[0] = (q[i] + b);//关键代码
//此时tme[0]是tme数组中最小的,q[i] > tme[0]说明此时tme[0]签到桌前没有队伍在签到
//那么第i队就在此签到，因为此桌是能最快签到的桌子，将tme[0]中数据更新为第i队签到后的时间
else tme[0] += b;//q[i] <= tme[0]说明在队伍到达时每一个桌子前都有其他队伍，需要排在该队伍后面，tme[0]更新为前一队签到后该队立即签完后的时间
}
sort(tme,tme+3);//再排列tme数组，此时tme中最后一个数tme[2]就是最大的
cout << tme[2] << endl;//输出最大的数就是全部队伍签到结束后所用的时间
}
return 0;
}
相关知识
牛客网的国庆自闭7天乐：一些好题
破解菜鸟算法题：新手必看的高效解题技巧与实战案例
阿凡题题库
一直刷不动算法题，怀疑人生？试试五毒掌法！
算法设计题解析
下载刷刷题APP,创建题库手机练习
衡量肥胖的方法包括体重指数法(BMI)、简易计算法和精确计算法,其中BMI=身高
李博生态学考研真题题库视频网课
牛客网——变种水仙花数
花中十二客中号称寿客的是( )
网址: 牛客题库快排算法：小杰的签到题 https://m.huajiangbk.com/newsview2568037.html
| 上一篇: 优秀新兴的民族体育健身之花—柔力 |
下一篇: 经过8年等待，日本军团再夺冬奥会 |
