PAT甲级1014Waiting in Line

题目介绍

  • 题目链接

    https://pintia.cn/problem-sets/994805342720868352/problems/994805498207911936

  • 题目考点

    队列和模拟,重难点在于模拟而非队列

  • 题目难度

    PAT甲级30分

  • 题目大意

    • 有N个窗口,每个窗口最多允许M个人站在黄线前排队,剩下的客户在黄线外等候。
    • 客户进入黄线时会选择人数最少的窗口排队,如果有重复,就选择索引最小的窗口
    • 客户$C_i$办理业务需要$T_i$分钟。
    • 前N个客户在8:00开始服务。
    • 请计算某个客户结束服务的时间。
  • 输入

    • N:正整数,不超过20,服务窗口的数量
    • M:正整数,不超过10,每个服务窗口前最多有几个人等待
    • K:正整数,不超过1000,顾客的数量,顾客索引为[1,K]
    • Q:要查询的顾客服务完成时间的数量
    • K个正整数:每个顾客完成服务需要几分钟
    • Q个正整数:需要查询的Q个顾客
  • 输出

    HH:MM的格式输出Q个顾客完成服务的时间,如果在17:00之前还没有开始服务,则输出Sorry。

题解

解题思路

  • 题目中有一个信息并没有十分明确地表达出来:黄线外的客户进入黄线以内时,索引小的人优先。根据这一点,所以从1到K遍历客户就可以。

  • 整体思路:计算出所有客户完成服务的时间,最后进行Q个查询并根据分钟数输出完成服务的时间(或sorry)

  • 如何计算出所有客户完成服务的时间?其实是个模拟题,核心在于入队,入队分2个阶段

  • 为什么核心是入队?某客户完成服务的时间取决于它前面1个客户完成服务的时间。而在某客户入队时,该客户前面就是队尾客户,所以该客户完成服务的时间=队尾客户完成服务的时间+该客户的服务时长。如果入队时队伍是空的,那该客户完成服务的时间就等于其服务所需时长。

  • 入队第1阶段是前N×M个客户入队

    无需等待黄线,只需按照客户索引顺序依次入队,其中前N个客户是在8:00开始服务。

    如何让这些客户正确地排队呢?用2层循环。内循环:在n个窗口中选择窗口(从1到N)入队。外循环:使内循环重复m次达到n×m的效果。这样就实现了“选择人数最少、索引最小的窗口”的要求。

    在客户入队时,我们需要不断更新客户索引,所以当已经没有客户时(即客户索引超过K时)要停止入队;另外所有窗口排满时也要停止入队,这通过双循环的判断条件实现。

  • 入队第2阶段是剩下的客户入队

    假如还有剩下的客户(即客户索引还未超过K时),那就要找出队伍最短的窗口,让下一个客户入队。

    如何找到队伍最短的窗口呢?在该方法中,并不是通过比较n个窗口的排队长度。因为如果还剩有客户就说明每个窗口都是满的,那队伍最短就没有意义了。而最快有客户结束服务的窗口(如果有重复,就选索引最小的窗口)就是队伍最短的窗口,也就是找到哪个窗口队首客户完成服务的时间最早。

  • 其它

    • 关于题目

      好久没做题目了,脑子和手都很生疏。看到这道题,我就想起来数学建模里做过的题、排队论什么的。思路很乱,我很自闭,这份题解的核心在于抓住了入队的规律。如果是更复杂的排队论问题,也许就需要模拟,模拟出一个时钟,然后某一分钟遍历所有窗口?这种思路确实可以,但效率不高。

    • 关于算法题

      脱离这道题来讲,模拟题(可能大多数算法题也是)都是找规律,然后用规律去求结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// Problem: PAT Advanced 1014
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805498207911936
// Tags: 队列

#include <iostream>
#include <queue>
using namespace std;

queue<int> window[20]; // n个窗口,每个窗口是一个排队队列
int processingTime[1001]; // k个客户需要的分钟数,index为[1,k]
int finishTime[1001]; // k个客户结束服务的时间,index为[1,k]

int main()
{
// 变量定义并初始化
int customerIndex = 1; // 客户索引,后面用来遍历客户
int n, m, k, q; // 窗口个数、单个窗口队伍最大长度、客户数量、查询数量
scanf("%d %d %d %d", &n, &m, &k, &q);
for (int i=1; i <= k; i++)
scanf("%d", processingTime+i);

// 处理前n×m个客户(内循环:在n个窗口中选择1个窗口入队。外循环:使内循环重复m次达到n×m的效果)
while(m--){
for (int j=0; j < n && customerIndex <= k; j++){ // 客户优先选择队伍最短、索引最小的窗口
if (window[j].empty()){ // 如果队伍是空的,那该客户在8:00开始服务,其完成服务的时间就等于其服务时长
finishTime[customerIndex] = processingTime[customerIndex];
}
else{
finishTime[customerIndex] = finishTime[window[j].back()] + processingTime[customerIndex]; // 该客户完成服务的时间=队尾客户完成服务的时间+该客户的服务时长
}
window[j].push(customerIndex); // 当前客户入队
customerIndex++; // 更新客户索引(考虑下一位客户)
}
}

// 如果还剩有客户的话,处理剩下的客户
while(customerIndex <= k){
int quickestFinishTime = finishTime[window[0].front()], quickestWindow = 0; // 找出队伍最短的窗口
for (int i=1; i < n; i++){
if (finishTime[window[i].front()] < quickestFinishTime){
quickestFinishTime = finishTime[window[i].front()];
quickestWindow = i;
}
}
finishTime[customerIndex] = finishTime[window[quickestWindow].back()] + processingTime[customerIndex]; // 记录当前客户结束服务的时间
window[quickestWindow].pop();
window[quickestWindow].push(customerIndex);

customerIndex++;
}

int query_customer;
while(q--){
scanf("%d", &query_customer);
if (finishTime[query_customer] - processingTime[query_customer] < 540){
printf("%02d:%02d\n", finishTime[query_customer]/60+8, finishTime[query_customer]%60);
}else{
printf("Sorry\n");
}
}
return 0;
}

参考链接


Github(github.com):@chouxianyu

Github Pages(github.io):@臭咸鱼

知乎(zhihu.com):@臭咸鱼

博客园(cnblogs.com):@臭咸鱼

B站(bilibili.com):@绝版臭咸鱼

微信公众号:@臭咸鱼

转载请注明出处,欢迎讨论和交流!