PAT – 第14页

PAT 乙级 1005. 继续(3n+1)猜想 (25) Java版

卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。

当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对n=3进行验证的时候，我们需要计算3、5、8、4、2、1，则当我们对n=5、8、4、2进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这4个数已经在验证3的时候遇到过了，我们称5、8、4、2是被3“覆盖”的数。我们称一个数列中的某个数n为“关键数”，如果n不能被数列中的其他数字所覆盖。

现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。

输入格式：每个测试输入包含1个测试用例，第1行给出一个正整数K(<100)，第2行给出K个互不相同的待验证的正整数n(1<n<=100)的值，数字间用空格隔开。

输出格式：每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用1个空格隔开，但一行中最后一个数字后没有空格。

输入样例：

6
3 5 6 7 8 11

1 2	6 3 5 6 7 8 11

输出样例：

7 6

7 6

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int k = in.nextInt();
		int[] n = new int[k];
		TreeSet[] treeSets = new TreeSet[k];
		for (int i = 0; i < k; i++) {
			n[i] = in.nextInt();
			treeSets[i] = new TreeSet<Integer>(getNumber(n[i]));
		}
		in.close();
		
		LinkedList<Integer> list = new LinkedList<Integer>();
		for (int i = 0; i < k; i++) {
			if (isMajor(n[i], treeSets, i)) {
				list.add(n[i]);
			}
		}
		
		int[] array = new int[list.size()];
		for (int i = 0; i < array.length; i++) {
			array[i] = list.get(i);
		}
		
		Arrays.sort(array);
		
		for (int i = array.length - 1; i > 0; i--) {
			System.out.print(array[i] + " ");
		}
		System.out.print(array[0]);
	}
	
	public static boolean isMajor(int n, TreeSet[] treeSets, int index) {
		for (int i = 0; i < treeSets.length; i++) {
			if (i != index && treeSets[i].contains(n)) {
				return false;
			}
		}
		return true;
	}
	public static TreeSet<Integer> getNumber(int n) {
		TreeSet<Integer> treeSet = new TreeSet<Integer>();
		treeSet.add(n);
		while (n != 1) {
			if (n % 2 == 0) {
				n = n / 2;
			} else {
				
				n = (3 * n + 1) / 2;
			}
			
			treeSet.add(n);
		}
		return treeSet;
	}
}

import java.util.Arrays;

import java.util.LinkedList;

import java.util.Scanner;

import java.util.TreeSet;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int k = in.nextInt();

int[] n = new int[k];

TreeSet[] treeSets = new TreeSet[k];

for (int i = 0; i < k; i++) {

n[i] = in.nextInt();

treeSets[i] = new TreeSet<Integer>(getNumber(n[i]));

}

in.close();

LinkedList<Integer> list = new LinkedList<Integer>();

for (int i = 0; i < k; i++) {

if (isMajor(n[i], treeSets, i)) {

list.add(n[i]);

}

int[] array = new int[list.size()];

for (int i = 0; i < array.length; i++) {

array[i] = list.get(i);

}

Arrays.sort(array);

for (int i = array.length - 1; i > 0; i--) {

System.out.print(array[i] + " ");

}

System.out.print(array[0]);

}

public static boolean isMajor(int n, TreeSet[] treeSets, int index) {

for (int i = 0; i < treeSets.length; i++) {

if (i != index && treeSets[i].contains(n)) {

return false;

}

return true;

}

public static TreeSet<Integer> getNumber(int n) {

TreeSet<Integer> treeSet = new TreeSet<Integer>();

treeSet.add(n);

while (n != 1) {

if (n % 2 == 0) {

n = n / 2;

} else {

n = (3 * n + 1) / 2;

}

treeSet.add(n);

}

return treeSet;

}

PAT 乙级 1002. 写出这个数 (20) Java版

读入一个自然数n，计算其各位数字之和，用汉语拼音写出和的每一位数字。

输入格式：每个测试输入包含1个测试用例，即给出自然数n的值。这里保证n小于10¹⁰⁰。

输出格式：在一行内输出n的各位数字之和的每一位，拼音数字间有1 空格，但一行中最后一个拼音数字后没有空格。

输入样例：

1234567890987654321123456789

1	1234567890987654321123456789

输出样例：

yi san wu

yi san wu

import java.util.*;
public class Main {
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String n = in.nextLine();
    in.close();

    int sum = 0;
    for (int i = 0; i < n.length(); i++) {
      sum += n.charAt(i) - '0';
    }

    Stack<String> stack = new Stack<>();
    String[] s = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};
    do {
      stack.push(s[sum % 10]);
      sum /= 10;
    } while (sum != 0);

    System.out.print(stack.pop());
    while (!stack.isEmpty()) {
      System.out.print(" " + stack.pop());
    }
  }
}

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

String n = in.nextLine();

in.close();

int sum = 0;

for (int i = 0; i < n.length(); i++) {

sum += n.charAt(i) - '0';

}

Stack<String> stack = new Stack<>();

String[] s = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};

do {

stack.push(s[sum % 10]);

sum /= 10;

} while (sum != 0);

System.out.print(stack.pop());

while (!stack.isEmpty()) {

System.out.print(" " + stack.pop());

}

1026. Table Tennis (30)-PAT甲级真题（模拟）

A table tennis club has N tables available to the public. The tables are numbered from 1 to N. For any pair of players, if there are some tables open when they arrive, they will be assigned to the available table with the smallest number. If all the tables are occupied, they will have to wait in a queue. It is assumed that every pair of players can play for at most 2 hours.

Your job is to count for everyone in queue their waiting time, and for each table the number of players it has served for the day.

One thing that makes this procedure a bit complicated is that the club reserves some tables for their VIP members. When a VIP table is open, the first VIP pair in the queue will have the priviledge to take it. However, if there is no VIP in the queue, the next pair of players can take it. On the other hand, if when it is the turn of a VIP pair, yet no VIP table is available, they can be assigned as any ordinary players.

Input Specification:

Each input file contains one test case. For each case, the first line contains an integer N (<=10000) – the total number of pairs of players. Then N lines follow, each contains 2 times and a VIP tag: HH:MM:SS – the arriving time, P – the playing time in minutes of a pair of players, and tag – which is 1 if they hold a VIP card, or 0 if not. It is guaranteed that the arriving time is between 08:00:00 and 21:00:00 while the club is open. It is assumed that no two customers arrives at the same time. Following the players’ info, there are 2 positive integers: K (<=100) – the number of tables, and M (< K) – the number of VIP tables. The last line contains M table numbers.

Output Specification:

For each test case, first print the arriving time, serving time and the waiting time for each pair of players in the format shown by the sample. Then print in a line the number of players served by each table. Notice that the output must be listed in chronological order of the serving time. The waiting time must be rounded up to an integer minute(s). If one cannot get a table before the closing time, their information must NOT be printed.

Sample Input:
9
20:52:00 10 0
08:00:00 20 0
08:02:00 30 0
20:51:00 10 0
08:10:00 5 0
08:12:00 10 1
20:50:00 10 0
08:01:30 15 1
20:53:00 10 1
3 1
2
Sample Output:
08:00:00 08:00:00 0
08:01:30 08:01:30 0
08:02:00 08:02:00 0
08:12:00 08:16:30 5
08:10:00 08:20:00 10
20:50:00 20:50:00 0
20:51:00 20:51:00 0
20:52:00 20:52:00 0
3 3 2

题目大意：k张桌子，球员到达后总是选择编号最小的桌子。如果训练时间超过2h会被压缩成2h，如果到达时候没有球桌空闲就变成队列等待。
k张桌子中m张是vip桌，如果vip桌子有空闲，而且队列里面有vip成员，那么等待队列中的第一个vip球员会到最小的vip球桌训练。如果vip桌子空闲但是没有vip来，那么就分配给普通的人。如果没有vip球桌空闲，那么vip球员就当作普通人处理。
给出每个球员的到达时间、要玩多久、是不是vip（是为1不是为0）。给出球桌数和所有vip球桌的编号，QQ所有在关门前得到训练的球员的到达时间、训练开始时间、等待时长（取整数，四舍五入），营业时间为8点到21点。如果再21点后还没有开始玩的人，就不再玩，不需要输出～

分析：在变量t中将输入时间转化为秒的形式，使用T数组存储某个时刻到达的客户玩耍的时间，使用V数组记录某个时刻到达的客户是否是VIP，在vip数组中存储某张桌子是不是vip专属，Table记录每个桌子上的客户剩余使用时间，队列Wait，vWait记录还在排队的普通、VIP客户，now记录当前要去玩耍的客户的到达时刻，nowt记录当前要去玩耍的桌子，num数组记录每张桌子使用的人数，AnsI数组和AnsO数组分别记录客户的到达时刻和开始玩耍时刻，table与vtalbe分别记录当前可使用的最小的普通、VIP桌子。思路：将客户到达时间的时分秒统一转换为秒，同时注意每对客户最多让玩2个小时。以秒为单位，遍历从8点到21点的每个时刻，判断当前是否有新到达的普通或VIP客户，将其加入对应的队列中。同时遍历每张桌子，将有人的桌子的客户剩余游玩时刻-1，同时判断空闲的最小编号的普通、VIP桌子编号。当VIP排队队列有人时，判断是否有空的VIP桌子，有的话直接进行记录；如果没有，判断是否有空缺的普通桌子，并是否存在更早到的普通客户；没有的话，就记录当前VIP客户使用了普通桌子。同理，判断普通客户的桌子使用情况。在输出时，将秒转化为时、分、秒的格式即可~

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
int n, m, k, H, M, S, t, table, vtable, cnt, now, nowt, T[100000], V[100000], num[10001], AnsI[10001], AnsO[10001], vip[10001];
map<int, int> Table;
queue<int> Wait, vWait;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d:%d:%d", &H, &M, &S);
        t = H * 3600 + M * 60 + S;
        scanf("%d %d", &T[t], &V[t]);
        T[t] = min(T[t], 120) * 60;
    }
    scanf("%d %d", &m, &k);
    for (int i = 0; i < k; i++) {
        scanf("%d", &t);
        vip[t] = 1;
    }
    for (int Time = 28800; Time < 75600; Time++, table = vtable = now = 0) {
        if (T[Time] && V[Time]) vWait.push(Time);
        else if (T[Time]) Wait.push(Time);
        for (int i = 1; i <= m; i++) {
            if (Table[i] > 0) Table[i]--;
            if (Table[i] == 0 && vip[i] && vtable == 0) vtable = i;
            if (Table [i] == 0 && table == 0) table = i;
        }
        if (!vWait.empty() && (table || vtable)) {
            now = vWait.front();
            nowt = vtable;
            if (vtable != 0) vWait.pop();
            else {
                nowt = table;
                if (!Wait.empty() && Wait.front() < vWait.front()) {
                    now = Wait.front();
                    Wait.pop();
                } else vWait.pop();
            }
        } else if (!Wait.empty() && (table || vtable)) {
            if (table != 0) nowt = table;
            else nowt = vtable;
            now = Wait.front();
            Wait.pop();
        }
        if (now == 0) continue;
        Table[nowt] = T[now];
        AnsI[cnt] = now;
        AnsO[cnt++] = Time;
        num[nowt]++;
    }
    for (int i = 0; i < cnt; i++)
        printf("%02d:%02d:%02d %02d:%02d:%02d %d\n", AnsI[i] / 3600, AnsI[i] % 3600 / 60, AnsI[i] % 60, AnsO[i] / 3600, AnsO[i] % 3600 / 60, AnsO[i] % 60, (AnsO[i] - AnsI[i] + 30) / 60);
    for (int i = 1; i <= m; i++) {
        if (i != 1) printf(" ");
        printf("%d", num[i]);
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <queue>

#include <map>

using namespace std;

int n, m, k, H, M, S, t, table, vtable, cnt, now, nowt, T[100000], V[100000], num[10001], AnsI[10001], AnsO[10001], vip[10001];

map<int, int> Table;

queue<int> Wait, vWait;

int main() {

scanf("%d", &n);

for (int i = 0; i < n; i++) {

scanf("%d:%d:%d", &H, &M, &S);

t = H * 3600 + M * 60 + S;

scanf("%d %d", &T[t], &V[t]);

T[t] = min(T[t], 120) * 60;

}

scanf("%d %d", &m, &k);

for (int i = 0; i < k; i++) {

scanf("%d", &t);

vip[t] = 1;

}

for (int Time = 28800; Time < 75600; Time++, table = vtable = now = 0) {

if (T[Time] && V[Time]) vWait.push(Time);

else if (T[Time]) Wait.push(Time);

for (int i = 1; i <= m; i++) {

if (Table[i] > 0) Table[i]--;

if (Table[i] == 0 && vip[i] && vtable == 0) vtable = i;

if (Table [i] == 0 && table == 0) table = i;

}

if (!vWait.empty() && (table || vtable)) {

now = vWait.front();

nowt = vtable;

if (vtable != 0) vWait.pop();

else {

nowt = table;

if (!Wait.empty() && Wait.front() < vWait.front()) {

now = Wait.front();

Wait.pop();

} else vWait.pop();

}

} else if (!Wait.empty() && (table || vtable)) {

if (table != 0) nowt = table;

else nowt = vtable;

now = Wait.front();

Wait.pop();

}

if (now == 0) continue;

Table[nowt] = T[now];

AnsI[cnt] = now;

AnsO[cnt++] = Time;

num[nowt]++;

}

for (int i = 0; i < cnt; i++)

printf("%02d:%02d:%02d %02d:%02d:%02d %d\n", AnsI[i] / 3600, AnsI[i] % 3600 / 60, AnsI[i] % 60, AnsO[i] / 3600, AnsO[i] % 3600 / 60, AnsO[i] % 60, (AnsO[i] - AnsI[i] + 30) / 60);

for (int i = 1; i <= m; i++) {

if (i != 1) printf(" ");

printf("%d", num[i]);

}

return 0;

}

1095. Cars on Campus (30)-PAT甲级真题（map，排序）

Zhejiang University has 6 campuses and a lot of gates. From each gate we can collect the in/out times and the plate numbers of the cars crossing the gate. Now with all the information available, you are supposed to tell, at any specific time point, the number of cars parking on campus, and at the end of the day find the cars that have parked for the longest time period.

Input Specification:

Each input file contains one test case. Each case starts with two positive integers N (<= 10000), the number of records, and K (<= 80000) the number of queries. Then N lines follow, each gives a record in the format

plate_number hh:mm:ss status

where plate_number is a string of 7 English capital letters or 1-digit numbers; hh:mm:ss represents the time point in a day by hour:minute:second, with the earliest time being 00:00:00 and the latest 23:59:59; and status is either in or out.

Note that all times will be within a single day. Each “in” record is paired with the chronologically next record for the same car provided it is an “out” record. Any “in” records that are not paired with an “out” record are ignored, as are “out” records not paired with an “in” record. It is guaranteed that at least one car is well paired in the input, and no car is both “in” and “out” at the same moment. Times are recorded using a 24-hour clock.

Then K lines of queries follow, each gives a time point in the format hh:mm:ss. Note: the queries are given in ascending order of the times.

Output Specification:

For each query, output in a line the total number of cars parking on campus. The last line of output is supposed to give the plate number of the car that has parked for the longest time period, and the corresponding time length. If such a car is not unique, then output all of their plate numbers in a line in alphabetical order, separated by a space.

Sample Input:
16 7
JH007BD 18:00:01 in
ZD00001 11:30:08 out
DB8888A 13:00:00 out
ZA3Q625 23:59:50 out
ZA133CH 10:23:00 in
ZD00001 04:09:59 in
JH007BD 05:09:59 in
ZA3Q625 11:42:01 out
JH007BD 05:10:33 in
ZA3Q625 06:30:50 in
JH007BD 12:23:42 out
ZA3Q625 23:55:00 in
JH007BD 12:24:23 out
ZA133CH 17:11:22 out
JH007BD 18:07:01 out
DB8888A 06:30:50 in
05:10:00
06:30:50
11:00:00
12:23:42
14:00:00
18:00:00
23:59:00
Sample Output:
1
4
5
2
1
0
1
JH007BD ZD00001 07:20:09
题目大意：给出n个车牌号、时间点、进出状态的记录，然后查询k个时间点这时校园内的车辆个数。最后还要输出在校园里面呆的时间最长的车的车牌号，以及呆了多久的时间。如果有多辆车就按照它的字母从小到大输出车牌。
配对要求是，如果一个车多次进入未出，取最后一个值；如果一个车多次out未进入，取第一个值。
注意：一个车可能出入校园好多次，停车的时间应该取之和。
分析：为了简便，应该把小时和分钟都化简成秒数计算比较方便。
一开始所有车辆的id、时间和是进还是出（进的flag是1，出的flag是-1），对他们排序，先按照车牌号排序，再按照来的时间先后排序。
此后就能根据这样的排序后的顺序将所有满足条件（合法）的车辆进出记录保存到另一个数组里面。这个数组再按照时间先后排序。
因为多次询问值，为了避免超时，可以把他们的车辆数cnt数组先算出来。到时候直接取值就会比较快速。cnt[i]表示在i下标的记录的时间点的时候车辆的数量。数量可以由前一个数量+当前车辆的flag得到。
因为问询的时候是多个时间点按照从小到大的顺序，利用好这点能避免超时。如果上一个查询的index已经被记住，那么下一次就只需要从这个index开始找就可以了，避免重复寻找，浪费时间。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
using namespace std;
struct node {
    char id[10];
    int time, flag = 0;
};
bool cmp1(node a, node b) {
    if(strcmp(a.id, b.id) != 0)
        return strcmp(a.id, b.id) < 0;
    else
        return a.time < b.time;
}
bool cmp2(node a, node b) {
    return a.time < b.time;
}
int main() {
    int n, k, maxtime = -1, tempindex = 0;
    scanf("%d%d\n", &n, &k);
    vector<node> record(n), car;
    for(int i = 0; i < n; i++) {
        char temp[5];
        int h, m, s;
        scanf("%s %d:%d:%d %s\n", record[i].id, &h, &m, &s, temp);
        int temptime = h * 3600 + m * 60 + s;
        record[i].time = temptime;
        record[i].flag = strcmp(temp, "in") == 0 ? 1 : -1;
    }
    sort(record.begin(), record.end(), cmp1);
    map<string, int> mapp;
    for(int i = 0; i < n - 1; i++) {
        if(strcmp(record[i].id, record[i+1].id) == 0 && record[i].flag == 1 && record[i+1].flag == -1) {
            car.push_back(record[i]);
            car.push_back(record[i+1]);
            mapp[record[i].id] += (record[i+1].time - record[i].time);
            if(maxtime < mapp[record[i].id]) {
                maxtime = mapp[record[i].id];
            }
        }
    }
    sort(car.begin(), car.end(), cmp2);
    vector<int> cnt(n);
    for(int i = 0; i < car.size(); i++) {
        if(i == 0)
            cnt[i] += car[i].flag;
         else
            cnt[i] = cnt[i - 1] + car[i].flag;
    }
    for(int i = 0; i < k; i++) {
        int h, m, s;
        scanf("%d:%d:%d", &h, &m, &s);
        int temptime = h * 3600 + m * 60 + s;
        int j;
        for(j = tempindex; j < car.size(); j++) {
            if(car[j].time > temptime) {
                printf("%d\n", cnt[j - 1]);
                break;
            } else if(j == car.size() - 1) {
                printf("%d\n", cnt[j]);
            }
        }
        tempindex = j;
    }
    for(map<string, int>::iterator it = mapp.begin(); it != mapp.end(); it++) {
        if(it->second == maxtime)
            printf("%s ", it->first.c_str());
    }
    printf("%02d:%02d:%02d", maxtime / 3600, (maxtime % 3600) / 60, maxtime % 60);
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <string>

#include <map>

using namespace std;

struct node {

char id[10];

int time, flag = 0;

};

bool cmp1(node a, node b) {

if(strcmp(a.id, b.id) != 0)

return strcmp(a.id, b.id) < 0;

else

return a.time < b.time;

}

bool cmp2(node a, node b) {

return a.time < b.time;

}

int main() {

int n, k, maxtime = -1, tempindex = 0;

scanf("%d%d\n", &n, &k);

vector<node> record(n), car;

for(int i = 0; i < n; i++) {

char temp[5];

int h, m, s;

scanf("%s %d:%d:%d %s\n", record[i].id, &h, &m, &s, temp);

int temptime = h * 3600 + m * 60 + s;

record[i].time = temptime;

record[i].flag = strcmp(temp, "in") == 0 ? 1 : -1;

}

sort(record.begin(), record.end(), cmp1);

map<string, int> mapp;

for(int i = 0; i < n - 1; i++) {

if(strcmp(record[i].id, record[i+1].id) == 0 && record[i].flag == 1 && record[i+1].flag == -1) {

car.push_back(record[i]);

car.push_back(record[i+1]);

mapp[record[i].id] += (record[i+1].time - record[i].time);

if(maxtime < mapp[record[i].id]) {

maxtime = mapp[record[i].id];

}

sort(car.begin(), car.end(), cmp2);

vector<int> cnt(n);

for(int i = 0; i < car.size(); i++) {

if(i == 0)

cnt[i] += car[i].flag;

else

cnt[i] = cnt[i - 1] + car[i].flag;

}

for(int i = 0; i < k; i++) {

int h, m, s;

scanf("%d:%d:%d", &h, &m, &s);

int temptime = h * 3600 + m * 60 + s;

int j;

for(j = tempindex; j < car.size(); j++) {

if(car[j].time > temptime) {

printf("%d\n", cnt[j - 1]);

break;

} else if(j == car.size() - 1) {

printf("%d\n", cnt[j]);

}

tempindex = j;

}

for(map<string, int>::iterator it = mapp.begin(); it != mapp.end(); it++) {

if(it->second == maxtime)

printf("%s ", it->first.c_str());

}

printf("%02d:%02d:%02d", maxtime / 3600, (maxtime % 3600) / 60, maxtime % 60);

return 0;

}

1017. Queueing at Bank (25)-PAT甲级真题（模拟）

Suppose a bank has K windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his/her turn to be served and there is a window available. It is assumed that no window can be occupied by a single customer for more than 1 hour.

Now given the arriving time T and the processing time P of each customer, you are supposed to tell the average waiting time of all the customers.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 numbers: N (<=10000) – the total number of customers, and K (<=100) – the number of windows. Then N lines follow, each contains 2 times: HH:MM:SS – the arriving time, and P – the processing time in minutes of a customer. Here HH is in the range [00, 23], MM and SS are both in [00, 59]. It is assumed that no two customers arrives at the same time.

Notice that the bank opens from 08:00 to 17:00. Anyone arrives early will have to wait in line till 08:00, and anyone comes too late (at or after 17:00:01) will not be served nor counted into the average.

Output Specification:

For each test case, print in one line the average waiting time of all the customers, in minutes and accurate up to 1 decimal place.

Sample Input:
7 3
07:55:00 16
17:00:01 2
07:59:59 15
08:01:00 60
08:00:00 30
08:00:02 2
08:03:00 10
Sample Output:
8.2

题目大意：有n个客户，k个窗口。已知每个客户的到达时间和需要的时长，如果有窗口就依次过去，如果没有窗口就在黄线外等候（黄线外只有一个队伍，先来先服务），求客户的平均等待时长。银行开放时间为8点到17点，再8点之前不开门，8点之前来的人都要等待，在17点后来的人不被服务。

分析：用一个结构体存储客户的到达时间和办理业务时间~首先把所有hh:mm:ss格式的时间全化成以当天0点为基准的秒数。注意晚于17:00的客户不算在内～既然客户是排队的，那么排序后对于每个客户都是同样的处理方式～使用一个优先队列维护窗口办理完业务的时间～如果最早结束服务的窗口时间早于客户的到达时间，不需要等待，直接执行 q.push(p[i].come + p[i].time);否则客户的等待时间是q.top() – p[i].come～

PS：感谢@琦子块提供的更优解～

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 10005;
struct person {
    int come, time;
} p[maxn];
int cmp(person p1, person p2) { return p1.come < p2.come; }
int n, k, cnt, total;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        int hh, ss, mm, tt;
        scanf("%d:%d:%d %d", &hh, &mm, &ss, &tt);
        int sum = hh * 3600 + mm * 60 + ss;
        if (sum > 61200) continue;
        p[++cnt].time = tt * 60;
        p[cnt].come = sum;
    }
    sort(p + 1, p + 1 + cnt, cmp);
    priority_queue<int, vector<int>, greater<int> > q;
    for (int i = 1; i <= k; ++i) q.push(28800);
    for (int i = 1; i <= cnt; ++i) {
        if (q.top() <= p[i].come) {
            q.push(p[i].come + p[i].time);
            q.pop();
        } else {
            total += q.top() - p[i].come;
            q.push(q.top() + p[i].time);
            q.pop();
        }
    }
    (!cnt) ? printf("0.0\n") : printf("%.1lf", ((double)total/60.0)/(double) cnt);
    return 0;
}

#include <iostream>

#include <queue>

#include <algorithm>

using namespace std;

const int maxn = 10005;

struct person {

int come, time;

} p[maxn];

int cmp(person p1, person p2) { return p1.come < p2.come; }

int n, k, cnt, total;

int main() {

scanf("%d%d", &n, &k);

for (int i = 1; i <= n; i++) {

int hh, ss, mm, tt;

scanf("%d:%d:%d %d", &hh, &mm, &ss, &tt);

int sum = hh * 3600 + mm * 60 + ss;

if (sum > 61200) continue;

p[++cnt].time = tt * 60;

p[cnt].come = sum;

}

sort(p + 1, p + 1 + cnt, cmp);

priority_queue<int, vector<int>, greater<int> > q;

for (int i = 1; i <= k; ++i) q.push(28800);

for (int i = 1; i <= cnt; ++i) {

if (q.top() <= p[i].come) {

q.push(p[i].come + p[i].time);

q.pop();

} else {

total += q.top() - p[i].come;

q.push(q.top() + p[i].time);

q.pop();

}

(!cnt) ? printf("0.0\n") : printf("%.1lf", ((double)total/60.0)/(double) cnt);

return 0;

}

1014. Waiting in Line (30)-PAT甲级真题（queue的应用）

Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:

The space inside the yellow line in front of each window is enough to contain a line with M customers. Hence when all the N lines are full, all the customers after (and including) the (NM+1)st one will have to wait in a line behind the yellow line.
Each customer will choose the shortest line to wait in when crossing the yellow line. If there are two or more lines with the same length, the customer will always choose the window with the smallest number.
Customer[i] will take T[i] minutes to have his/her transaction processed.
The first N customers are assumed to be served at 8:00am.
Now given the processing time of each customer, you are supposed to tell the exact time at which a customer has his/her business done.

For example, suppose that a bank has 2 windows and each window may have 2 custmers waiting inside the yellow line. There are 5 customers waiting with transactions taking 1, 2, 6, 4 and 3 minutes, respectively. At 08:00 in the morning, customer1 is served at window1 while customer2 is served at window2. Customer3 will wait in front of window1 and customer4 will wait in front of window2. Customer5 will wait behind the yellow line.

At 08:01, customer1 is done and customer5 enters the line in front of window1 since that line seems shorter now. Customer2 will leave at 08:02, customer4 at 08:06, customer3 at 08:07, and finally customer5 at 08:10.

Input

Each input file contains one test case. Each case starts with a line containing 4 positive integers: N (<=20, number of windows), M (<=10, the maximum capacity of each line inside the yellow line), K (<=1000, number of customers), and Q (<=1000, number of customer queries).

The next line contains K positive integers, which are the processing time of the K customers.

The last line contains Q positive integers, which represent the customers who are asking about the time they can have their transactions done. The customers are numbered from 1 to K.

Output

For each of the Q customers, print in one line the time at which his/her transaction is finished, in the format HH:MM where HH is in [08, 17] and MM is in [00, 59]. Note that since the bank is closed everyday after 17:00, for those customers who cannot be served before 17:00, you must output “Sorry” instead.

Sample Input
2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7
Sample Output
08:07
08:06
08:10
17:00
Sorry

题目大意：n个窗口，每个窗口可以排队m人。有k位用户需要服务，给出了每位用户需要的minute数，所有客户在8点开始服务，如果有窗口还没排满就入队，否则就在黄线外等候。如果有某一列有一个用户走了服务完毕了，黄线外的人就进来一个。如果同时就选窗口数小的。求q个人的服务结束时间。
如果一个客户在17:00以及以后还没有开始服务（此处不是结束服务是开始17:00）就不再服务输出sorry；如果这个服务已经开始了，无论时间多长都要等他服务完毕。
分析：设立结构体，里面包含poptime为队首的人出队（结束）的时间，和endtime为队尾的人结束的时间。poptime是为了让黄线外的人可以计算出哪一个队列先空出人来（poptime最小的那个先有人服务完毕），endtime是为了入队后加上自己本身的服务所需时间可以计算出自己多久才能被服务完毕～且前一个人的endtime可以得知自己是不是需要被Sorry（如果前一个人服务结束时间超过17:00，自己当前入队的人就是sorry），还有一个queue表示所有当前该窗口的排队队列。
对于前m*n个人，也就是排的下的情况下，所有人依次到窗口前面排队。对于m*n之后的人，当前人选择poptime最短的入队，让队伍的第一个人出列），如果前面一个人导致的endtime超过17点就标记自己的sorry为true。
计算时间的时候按照分钟计算，最后再考虑08点开始和转换为小时分钟的形式会比较简便。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct node {
    int poptime, endtime;
    queue<int> q;
};
int main() {
    int n, m, k, q, index = 1;
    scanf("%d%d%d%d", &n, &m, &k, &q);
    vector<int> time(k + 1), result(k + 1);
    for(int i = 1; i <= k; i++) {
        scanf("%d", &time[i]);
    }
    vector<node> window(n + 1);
    vector<bool> sorry(k + 1, false);
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if(index <= k) {
                window[j].q.push(time[index]);
                if(window[j].endtime >= 540)
                    sorry[index] = true;
                window[j].endtime += time[index];
                if(i == 1)
                    window[j].poptime = window[j].endtime;
                result[index] = window[j].endtime;
                index++;
            }
            
        }
    }
    while(index <= k) {
        int tempmin = window[1].poptime, tempwindow = 1;
        for(int i = 2; i <= n; i++) {
            if(window[i].poptime < tempmin) {
                tempwindow = i;
                tempmin = window[i].poptime;
            }
        }
        window[tempwindow].q.pop();
        window[tempwindow].q.push(time[index]);
        window[tempwindow].poptime +=  window[tempwindow].q.front();
        if(window[tempwindow].endtime >= 540)
            sorry[index] = true;
        window[tempwindow].endtime += time[index];
        result[index] = window[tempwindow].endtime;
        index++;
    }
    for(int i = 1; i <= q; i++) {
        int query, minute;
        scanf("%d", &query);
        minute = result[query];
        if(sorry[query] == true) {
            printf("Sorry\n");
        } else {
            printf("%02d:%02d\n",(minute + 480) / 60, (minute + 480) % 60);
        }
    }
    return 0;
}

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

struct node {

int poptime, endtime;

queue<int> q;

};

int main() {

int n, m, k, q, index = 1;

scanf("%d%d%d%d", &n, &m, &k, &q);

vector<int> time(k + 1), result(k + 1);

for(int i = 1; i <= k; i++) {

scanf("%d", &time[i]);

}

vector<node> window(n + 1);

vector<bool> sorry(k + 1, false);

for(int i = 1; i <= m; i++) {

for(int j = 1; j <= n; j++) {

if(index <= k) {

window[j].q.push(time[index]);

if(window[j].endtime >= 540)

sorry[index] = true;

window[j].endtime += time[index];

if(i == 1)

window[j].poptime = window[j].endtime;

result[index] = window[j].endtime;

index++;

}

while(index <= k) {

int tempmin = window[1].poptime, tempwindow = 1;

for(int i = 2; i <= n; i++) {

if(window[i].poptime < tempmin) {

tempwindow = i;

tempmin = window[i].poptime;

}

window[tempwindow].q.pop();

window[tempwindow].q.push(time[index]);

window[tempwindow].poptime += window[tempwindow].q.front();

if(window[tempwindow].endtime >= 540)

sorry[index] = true;

window[tempwindow].endtime += time[index];

result[index] = window[tempwindow].endtime;

index++;

}

for(int i = 1; i <= q; i++) {

int query, minute;

scanf("%d", &query);

minute = result[query];

if(sorry[query] == true) {

printf("Sorry\n");

} else {

printf("%02d:%02d\n",(minute + 480) / 60, (minute + 480) % 60);

}

return 0;

}