1014 Waiting in Line

1014 Waiting in Line

题目描述

假设一家银行有 N 个窗口对外营业。每个窗口前都有一条黄线，将等候区划分为两部分。客户排队等候的规则如下：

  • 每个窗口前黄线内的区域最多可容纳 M 位客户排队。因此，当所有 N 条队伍都排满时，从第（N×M+1）位客户开始，都必须在黄线外等候。
  • 每位客户在跨过黄线时，会选择当前最短的队伍排队；如果有多条队伍长度相同，则总是选择编号最小的窗口。
  • 第 i 位客户办理业务需要花费 Tᵢ 分钟。
  • 前 N 位客户默认从早上 8:00 开始办理业务。

现在给定每位客户的业务办理时长，请你计算出每位客户完成业务的准确时间。

例如，假设银行有 2 个窗口，每个窗口黄线内最多容纳 2 位客户，现有 5 位客户等候，办理时长分别为 1、2、6、4、3 分钟。早上 8:00，客户₁ 在窗口₁ 办理，客户₂ 在窗口₂ 办理；客户₃ 排在窗口₁ 前，客户₄ 排在窗口₂ 前，客户₅ 则在黄线外等候。

8:01 客户₁ 办理完成，客户₅ 进入窗口₁ 队伍（此时该队伍更短）。最终客户₂ 在 8:02 完成，客户₄ 在 8:06 完成，客户₃ 在 8:07 完成，客户₅ 在 8:10 完成。

输入规格

每个输入文件包含一个测试用例。每个用例以 4 个正整数开头：

  • N（≤20）：窗口数量
  • M（≤10）：每个窗口黄线内队伍的最大容量
  • K（≤1000）：客户总数
  • Q（≤1000）：查询次数

接下来一行包含 K 个正整数，代表 K 位客户各自的业务办理时长。

最后一行包含 Q 个正整数，代表需要查询完成时间的客户编号（客户编号从 1 到 K）。

输出规格

对于每一个查询的客户，在一行中输出其业务办理完成的时间，格式为 HH:MM，其中 HH 范围为 [08, 17]，MM 范围为 [00, 59]。

注意：由于银行每天 17:00 关门，若客户无法在 17:00 前开始办理业务，则必须输出 Sorry 代替。

输入样例

2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7

输出样例

08:07
08:06
08:10
17:00
Sorry

题目考察点 📝

这道题是典型的模拟 + 队列 + 贪心类编程题，核心考察以下能力：

1. 多队列模拟能力

  • 用队列结构模拟银行多窗口排队场景，实现入队、出队、队列长度统计等基础操作。
  • 模拟时间流逝：当所有窗口黄线内队伍满员时，需找到最早完成服务的窗口，推进时间并更新各窗口剩余服务时长。

2. 贪心策略应用

  • 客户选队规则：优先选择当前最短队列，若队列长度相同则选择编号最小的窗口。
  • 黄线外客户等待规则：所有队伍满员时，等待最早完成服务的窗口，再按贪心规则入队。

3. 时间处理与格式转换

  • 时间统一转换为相对 08:00 的分钟数进行计算，简化时分运算。
  • 结果格式化为 HH:MM 格式，要求高位补零（如 08:07），且小时范围限定在 [08,17]。

4. 边界条件处理

  • 队列容量边界：黄线内最多容纳 M 人，超出客户在黄线外等待。
  • 银行关门边界：17:00 后才开始服务的客户无法办理业务。

题目易错点 ⚠️

1. 核心规则理解错误（最致命）

  • ❌ 误区：判断客户能否被服务，看结束时间是否超过 17:00。
  • ✅ 正确：判断开始服务时间是否 ≥ 17:00（540 分钟）。只要在 17:00 前开始服务，即使结束时间超过 17:00，也必须完成并输出结束时间；仅 17:00 及之后才开始服务的客户，输出 Sorry。

2. 时间流逝模拟错误

  • ❌ 误区：仅更新最早完成窗口的剩余时间，忽略其他窗口的时间也在同步推进。
  • ✅ 正确：找到最早完成的窗口后，所有窗口的剩余服务时间都要减去该窗口的剩余时长，模拟“时间向前推进”的过程。

3. 队列选择逻辑偏差

  • ❌ 误区：仅比较队列当前人数，或长度相同时选择编号更大的窗口。
  • ✅ 正确：优先选人数最少的队列，人数相同时必须选编号最小的窗口，这是题目明确要求的贪心规则。

4. 时间计算逻辑混乱

  • ❌ 误区：直接用“当前时间 + 服务时长”计算结束时间，未考虑前面客户的排队等待时间。
  • ✅ 正确：
    • 开始服务时间 = 窗口已完成服务总时间 + 队列中前面所有客户的服务时长之和
    • 结束服务时间 = 开始服务时间 + 当前客户服务时长

5. 输出格式不规范

  • ❌ 误区：时分格式未补零（如 8:7），或 17:00 之后开始的客户错误输出结束时间。
  • ✅ 正确：使用 %02d:%02d 格式化输出，严格判断开始服务时间，不符合条件则输出 Sorry。

6. 队列满员后处理遗漏

  • ❌ 误区：未处理黄线外客户的等待逻辑，或在队伍未满时就让客户在黄线外等待。
  • ✅ 正确：仅当所有窗口黄线内队伍都满员（总人数 = N×M）时，后续客户才在黄线外等待，直到有窗口完成服务后再入队。

C语言解题

/**
 * @file 1014_WaitingInLine.c
 * @brief 银行排队模拟问题（PAT 1014题）
 * @details 模拟银行多窗口排队场景，计算客户的开始服务时间和结束服务时间，
 *          核心规则：17:00（相对08:00的540分钟）后开始服务的客户无法办理，输出Sorry；
 *          17:00前开始服务的客户需完成服务并输出结束时间（HH:MM格式）。
 * @author Your Name
 * @date 2026-03-24
 */

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>

 /**
  * @def CLOSE_TIME
  * @brief 银行关门的时间阈值（相对08:00的分钟数），即17:00 = 9*60 = 540分钟
  */
#define CLOSE_TIME 540

  /**
   * @def MAX_QUEUE
   * @brief 每个窗口队列的最大容量上限
   */
#define MAX_QUEUE 1000

   /**
    * @struct QueueWindow
    * @brief 单个窗口的队列结构，包含队列存储、指针、计数和队首剩余服务时间
    * @var QueueWindow::q
    * 队列存储数组，存放客户的服务时长
    * @var QueueWindow::front
    * 队列头指针（出队位置）
    * @var QueueWindow::rear
    * 队列尾指针（入队位置）
    * @var QueueWindow::count
    * 队列当前元素个数（黄线内排队人数）
    * @var QueueWindow::top_left_time
    * 队首客户的剩余服务时间
    */
typedef struct {
    int *q;
    int front, rear;
    int count;
    int top_left_time;
} QueueWindow;

/**
 * @brief 初始化窗口队列
 * @param window [out] 指向QueueWindow结构体的指针，待初始化的窗口队列
 * @return 无返回值
 */
void init_queue(QueueWindow *window)
{
    window->q = (int*)malloc(sizeof(int) * MAX_QUEUE);
    window->front = window->rear = 0;
    window->count = 0;
    window->top_left_time = 0;
}

/**
 * @brief 释放单个窗口队列的内存
 * @param window [in/out] 待释放的窗口队列
 * @return 无返回值
 */
void free_queue_window(QueueWindow *window)
{
    if (window->q != NULL) {
        free(window->q);
        window->q = NULL; // 置空避免野指针
    }
    window->front = window->rear = 0;
    window->count = 0;
    window->top_left_time = 0;
}

/**
 * @brief 释放所有窗口队列的内存（批量释放）
 * @param windows [in/out] 所有窗口队列的数组
 * @param size [in] 窗口总数（数组长度）
 * @return 无返回值
 */
void free_all_windows(QueueWindow *windows, int size)
{
    if (windows != NULL) {
        // 先释放每个窗口的内部队列内存
        for (int i = 0; i < size; i++) {
            free_queue_window(&windows[i]);
        }
        // 再释放窗口数组本身
        free(windows);
    }
}

/**
 * @brief 入队操作：将客户服务时长加入窗口队列
 * @param window [in/out] 目标窗口队列
 * @param val [in] 要入队的客户服务时长
 * @return 无返回值
 */
void enqueue(QueueWindow *window, int val)
{
    if (window->rear < MAX_QUEUE) {
        window->q[window->rear] = val;
        window->rear++;
        window->count++;
    }
}

/**
 * @brief 出队操作：移除并返回队首元素
 * @param window [in/out] 目标窗口队列
 * @return 成功出队返回队首元素（客户服务时长），队列为空返回-1
 */
int dequeue(QueueWindow *window)
{
    if (window->front < window->rear) {
        window->count--;
        return window->q[window->front++];
    }
    return -1;
}

/**
 * @brief 判断窗口队列是否为空
 * @param window [in] 目标窗口队列
 * @return 空返回1，非空返回0
 */
int is_queue_empty(QueueWindow *window)
{
    return (window->front == window->rear && window->count == 0);
}

/**
 * @brief 获取队列当前元素个数（队列长度）
 * @param window [in] 目标窗口队列
 * @return 队列长度（rear - front）
 */
int get_queue_size(QueueWindow *window)
{
    return (window->rear - window->front);
}

/**
 * @brief 获取队首元素（未出队）
 * @param window [in] 目标窗口队列
 * @return 队首元素值（客户服务时长）
 */
int get_queue_top(QueueWindow *window)
{
    return window->q[window->front];
}

/**
 * @brief 计算队列中所有元素的总和（当前队列所有客户的服务时长总和）
 * @param window [in] 目标窗口队列
 * @return 队列元素总和
 */
int get_queue_sum(QueueWindow *window)
{
    int sum = 0;
    for (int i = window->front; i < window->rear; i++) {
        sum += window->q[i];
    }
    return sum;
}

/**
 * @brief 获取队首客户的剩余服务时间
 * @param window [in] 目标窗口队列
 * @return 队首剩余服务时间
 */
int get_top_left_time(QueueWindow *window)
{
    return window->top_left_time;
}

/**
 * @brief 更新队首客户的剩余服务时间
 * @param window [in/out] 目标窗口队列
 * @param flag [in] 更新类型：<0=减少时间，>0=增加时间，0=重置为队首元素值
 * @param val [in] 要增减的时间值（flag=0时无意义）
 * @return 无返回值
 */
void update_top_left_time(QueueWindow *window, int flag, int val)
{
    if (flag < 0) {
        window->top_left_time -= val;
    }
    else if (flag > 0) {
        window->top_left_time += val;
    }
    else {
        window->top_left_time = is_queue_empty(window) ? 0 : get_queue_top(window);
    }
}

/**
 * @brief 当某窗口队首完成服务时，更新其他所有窗口的剩余服务时间（模拟时间流逝）
 * @param windows [in/out] 所有窗口队列的数组
 * @param size [in] 窗口总数（数组长度）
 * @param idx [in] 最早完成服务的窗口索引
 * @return 无返回值
 */
void update_other_left_time(QueueWindow *windows, int size, int idx)
{
    int val = windows[idx].top_left_time;
    for (int i = 0; i < size; i++) {
        if (i == idx) continue;
        update_top_left_time(&windows[i], -1, val);
    }
}

/**
 * @brief 核心计算函数：计算每个客户的开始服务时间和结束服务时间
 * @param N [in] 窗口总数
 * @param M [in] 每个窗口黄线内的最大排队人数
 * @param K [in] 客户总数
 * @param T [in] 客户服务时长数组（T[1..K]有效，T[0]未使用）
 * @param start_time [out] 客户开始服务时间数组（相对08:00的分钟数）
 * @param finish_time [out] 客户结束服务时间数组（相对08:00的分钟数）
 * @return 无返回值
 */
void calc_finish_time(int N, int M, int K, int *T, int *start_time, int *finish_time)
{
    // 初始化所有窗口队列
    QueueWindow *windows = (QueueWindow*)malloc(sizeof(QueueWindow) * N);
    if (windows == NULL) return;
    for (int i = 0; i < N; i++) {
        init_queue(&windows[i]);
    }

    // 记录每个窗口累计完成的服务时间总和
    int *window_finish_sum = (int*)malloc(sizeof(int) * N);
    if (window_finish_sum == NULL) {
        free_all_windows(windows, N); // 内存分配失败时提前释放
        return;
    }
    memset(window_finish_sum, 0, sizeof(int) * N);

    // 逐个客户分配窗口并计算时间
    for (int i = 1; i <= K; i++) {
        int target_win = -1;        // 目标窗口索引
        int all_win_full = 1;       // 所有窗口是否满员标志
        int min_win_cnt = INT_MAX;  // 当前最小队列长度

        // 第一步：查找未满员的窗口（优先选最短队列，长度相同选编号最小）
        for (int j = 0; j < N; j++) {
            if (windows[j].count < M) {
                all_win_full = 0;
                if (windows[j].count < min_win_cnt) {
                    target_win = j;
                    min_win_cnt = windows[j].count;
                }
            }
        }

        int wait_time = 0;  // 客户在队列中的等待时间（前面客户的服务时长总和）
        // 情况一：所有窗口黄线内都满员 → 等待最早完成的窗口
        if (all_win_full) {
            int min_top_left_time = INT_MAX;
            // 找到队首剩余时间最短的窗口
            for (int j = 0; j < N; j++) {
                int top_left_time = get_top_left_time(&windows[j]);
                if (top_left_time < min_top_left_time) {
                    target_win = j;
                    min_top_left_time = top_left_time;
                }
            }

            // 所有窗口减去最短剩余时间（模拟时间推进）
            update_other_left_time(windows, N, target_win);
            // 队首客户完成服务，更新窗口累计完成时间
            window_finish_sum[target_win] += dequeue(&windows[target_win]);
            // 计算当前客户的排队等待时间
            wait_time = get_queue_sum(&windows[target_win]);
            // 当前客户入队
            enqueue(&windows[target_win], T[i]);
            // 重置队首剩余服务时间
            update_top_left_time(&windows[target_win], 0, 0);
        }
        // 情况二：有未满员的窗口 → 直接进入最短队列
        else {
            wait_time = is_queue_empty(&windows[target_win]) ? 0 : get_queue_sum(&windows[target_win]);
            enqueue(&windows[target_win], T[i]);
            // 若队列原本为空，初始化队首剩余服务时间
            if (get_queue_size(&windows[target_win]) == 1) {
                update_top_left_time(&windows[target_win], 0, 0);
            }
        }

        // 计算当前客户的开始/结束服务时间
        start_time[i] = window_finish_sum[target_win] + wait_time;
        finish_time[i] = window_finish_sum[target_win] + wait_time + T[i];
        // 调试输出：可注释
        printf("客户%d → 窗口%d : 开始=%d, 结束=%d\n", i, target_win, start_time[i], finish_time[i]);
    }

    // 释放内存（调用封装函数）
    free_all_windows(windows, N);
    free(window_finish_sum);
}

/**
 * @brief 主函数：处理输入、调用计算函数、输出查询结果
 * @return 程序执行状态码（0=成功，1=内存分配失败）
 */
int main()
{
    int N, M, K, Q; // N=窗口数，M=黄线内人数，K=客户数，Q=查询数
    scanf("%d %d %d %d", &N, &M, &K, &Q);

    // 分配客户服务时长数组（索引1~K有效）
    int *T = (int*)malloc(sizeof(int) * (K + 1));
    if (T == NULL) return 1;
    for (int i = 1; i <= K; i++) {
        scanf("%d", &T[i]);
    }

    // 分配开始/结束时间数组
    int *finish_time = (int*)malloc(sizeof(int) * (K + 1));
    if (finish_time == NULL) {
        free(T);
        return 1;
    }
    memset(finish_time, 0, sizeof(int) * (K + 1));

    int *start_time = (int*)malloc(sizeof(int) * (K + 1));
    if (start_time == NULL) {
        free(T);
        free(finish_time);
        return 1;
    }
    memset(start_time, 0, sizeof(int) * (K + 1));

    // 计算所有客户的开始/结束时间
    calc_finish_time(N, M, K, T, start_time, finish_time);

    // 处理查询请求
    int query_idx;
    for (int i = 0; i < Q; i++) {
        scanf("%d", &query_idx);
        if (query_idx < 1 || query_idx > K) continue;

        // 核心判断：开始服务时间 < 540分钟（17:00）→ 可服务，否则输出Sorry
        if (start_time[query_idx] < CLOSE_TIME) {
            // 转换为HH:MM格式（08:00为基准）
            int hour = 8 + finish_time[query_idx] / 60;
            int minute = finish_time[query_idx] % 60;
            printf("%02d:%02d\n", hour, minute);
        }
        else {
            printf("Sorry\n");
        }
    }

    // 释放内存
    free(T);
    free(finish_time);
    free(start_time);
    return 0;
}
# c语言 # 算法 # 数据结构 # 贪心算法 # 经验分享 # visual studio
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

cover

【AI】从混沌到精准：LLM 结构化信息抽取的提示词迭代之路

avatar AtomGit开源社区
cover

Tranformer 代码实现3：手搓 FNN 层

avatar AtomGit开源社区
cover

【深度收藏】从“手“到“说明书“，一文看懂AI Agent的Function Calling、MCP和Skills

avatar AtomGit开源社区