【题解】PAT 1014 Waiting in Line

原题链接：1014 Waiting in Line

读题，有K个客户和N个窗口，每个窗口前可以排M个人长的队，没排上队的客户在黄线之外等待，若有位置了就去排队，客户选择队伍的方式为：

1. 选择人数最少的
2. 人数相同，选择编号最小的

银行在08:00开始营业，17:00关门，总共9小时，540分钟（注意，如果客户在17:00前开始进行服务，则一直到其完成业务之后才关门）

• 如果客户人数少于M*N，那么就全部直接进入黄线排队即可
• 否则，先让前M*N个人入队，其他人在黄线外等待
  • 建立两个数组，队列数组record记录该队列中每个客户完成业务的时间，int数组back记录每个队列数组record最后的元素
  • 处理黄线外客户的业务时，首先找到record中队头元素最小的那一个，然后队头客户出队，将该客户入队，并更新back数组

#include 
using namespace std;
const int len = 1001;

int main () {
    int ans[len]; // 用于记录最后客户的离队时间
    int n,m,k,q, time, id; scanf("%d %d %d %d", &n, &m, &k, &q);

    if (k <= n*m) {
        int back[20] = {0};
        for (int i=1;i<=k;i++) {
            scanf("%d", &time);

            if (back[i%n] >= 540) ans[i]=-1;
            else ans[i] = back[i%n]+time;

            back[i%n]+=time;
        }
    } else {
        int back[20] = {0};
        queue record[20];
        for (int i=1;i<=n*m;i++) {
            scanf("%d", &time);

            if (back[(i-1)%n] >= 540) ans[i]=-1;
            else ans[i] = back[(i-1)%n]+time;

            back[(i-1)%n]+=time;
            record[(i-1)%n].push(back[(i-1)%n]);
        }

        for (int i=n*m+1;i<=k;i++) {
            scanf("%d", &time);
            id = 0; for (int j=1;j= 540) ans[i]=-1;
            else ans[i] = back[id]+time;

            record[id].pop();back[id]+=time;record[id].push(back[id]);
        }
    }

    for(int i=0;i
        scanf("%d", &id);
        if (id > k) {
            printf("Sorryn");
            continue;
        }
        time = ans[id];
        if (time == -1) printf("Sorryn");
        else printf("%02d:%02dn", 8+time/60, time%60);
    }

    return 0;
}

#include 
using namespace std;
const int len = 1001;

int main () {
    int ans[len]; // 用于记录最后客户的离队时间
    int n,m,k,q, time, id; scanf("%d %d %d %d", &n, &m, &k, &q);

    if (k <= n*m) {
        int back[20] = {0};
        for (int i=0;i
            scanf("%d", &time);

            if (back[i%n] >= 540) ans[i]=-1;
            else ans[i] = back[i%n]+time;

            back[i%n]+=time;
        }
    } else {
        int back[20] = {0};
        queue record[20];
        for (int i=1;i<=n*m;i++) {
            scanf("%d", &time);

            if (back[(i-1)%n] >= 540) ans[i]=-1;
            else ans[i] = back[(i-1)%n]+time;

            back[(i-1)%n]+=time;
            record[(i-1)%n].push(back[(i-1)%n]);
        }

        for (int i=n*m+1;i<=k;i++) {
            scanf("%d", &time);
            id = 0; for (int j=1;j= 540) ans[i]=-1;
            else ans[i] = back[id]+time;

            record[id].pop();back[id]+=time;record[id].push(back[id]);
        }
    }

    for(int i=0;i
        scanf("%d", &id);
        if (id > k) {
            printf("Sorryn");
            continue;
        }
        time = ans[id];
        if (time == -1) printf("Sorryn");
        else printf("%02d:%02dn", 8+time/60, time%60);
    }

    return 0;
}