1026 Table Tennis (30分) 难度不高 + 逻辑复杂 +细节繁琐

题目

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

题目解读

某乒乓球场每天服务时间是8:00 -- 21:00，有·K个桌子（编号 1-K），其中M个为会员预留，某一天，有N个玩家要来打球，给出了他们的到达时间，玩耍时间，和他们是否是会员，要求，输出这些玩家的 到达时间 开始被服务时间 玩耍时间。输出每个桌子服务的人数。

需要注意的是：

• 21:00及之后到来的玩家无法被服务，这些玩家不用考虑；
• 由于排队等待导致21:00前还未能被服务的玩家也要在输出中排除；
• 每个乒乓球求桌子限制最多一次服务2个小时；
• 所有的输出顺序要按照玩家开始被服务时间的先后顺序。
• vip玩家的服务优先级高于普通玩家。当没有会员来时，vip桌子也为普通用户服务。这个的具体理解我在思路中细说。

思路解析

说实话这个题目难度不高，无非就是先来先服务，也就是所有玩家按照到达的先后顺序排序然后逐个处理，只不过vip可以" 插队 " 就导致分类讨论比较复杂一点。

框架步骤

1. 创建结构体 Player 保存玩家的 到达时间、开始被服务时间、玩耍时间、是否是会员。

	struct Player {
	    // 到达时间，开始时间，玩耍时间
	    int arrive_time, start_time, play_time;
	    bool isvip; // 是否是 vip
	};

1. 创建结构体 Table 保存每个桌子 何时结束当前服务、服务了几个人、是不是为vip预留。所有桌子刚开始都是8:00开始服务，所以 end_time 字段初始化为 8 * 3600。

	struct Table {
	    // 当前服务结束时间，已服务玩家个数
	    // 刚开始全是8:00开始服务
	    int end_time = club_open_time, serve_count;
	    bool isvip; // 是否是为vip预留的桌子
	};

1. 用vector保存玩家信息和桌子信息。
2. 把所有时间都转换为以 00:00:00 开始的秒数进行处理。
3. 逐个读入玩家的信息，对于到达时间在 21:00及之后的不予理睬。对于”合法“用户，如果玩耍时间超过两小时，将其值赋为7200s，将被开始服务时间初始化为 21:00，这样做的目的是，所有得到服务的玩家这个字段一定会被改变成小于 21:00 的时间，最终在输出时能很方便的过滤掉那些未被服务的玩家信息。
4. 对所有玩家按照到达时间进行排序。
5. 逐个处理”玩家“，分类四种讨论，我们下面单独拿出来说它。
6. 处理完所有玩家，按照被服务的开始时间排序
7. 输出结果（过率掉未被服务玩家）

第7步细说（对每个玩家的处理）

1. 找到所有桌子中最早结束当前服务的桌子，序号为 index。

2. 如果这个桌子当前服务的结束时间 >= 21 * 3600，那剩下的玩家都不用处理了，不可能被服务。否则再继续下面的过程。

3. 如果这个桌子是为vip预留的：
   
   3.1 如果这个人是vip，这个桌子分配给他。i++ 处理下一个人
   
   3.2 这个人不是vip，除非他后面没有vip到来，桌子才给他用：

   找到他后面第一个vip；

   1. 如果vip不存在，那么这个桌子给直接给他用。
   2. 如果vip存在，那么这个桌子给vip用，对吗？？？注意这是错误的！！！除非这个vip在这个桌子当前服务结束之前来了，这个vip才能插队啊。他都没来插什么队。
   3. 你不是说vip存在了吗？存在了为什么又说他没来。你要区分现实生活和程序的区别，现实生活中你一眼看到你后面没有人你说不存在，但程序一次性把所有人信息都保存在数组里了，你肉眼去看数组元素肯定存在啊，但是你要去看他的到达时间是不是在这个窗口结束当前服务之间，如果不是，那就是说这个窗口结束服务了，但是，我后面那个所谓”存在“的vip没有到达，不就相当于没有吗？好好想一下，我就是漏了这个一个条件，只得了15分，就在if里面加上一个 && xxxx，立马满分！

4. 如果这个桌子是普通桌子：
   
   4.1 如果这个人是普通人，那么这个桌子分配给他。i++ 处理下一个人
   
   4.2 如果这个人是vip，首先去看在他来之前有没有空下来的vip桌子，如果有，就让他去那个vip桌子，如果没有，就把这个普通桌子给他用。i++ 处理下一个人。

现在我们要处理两个问题

1. 分配桌子是干嘛？

   把某个桌子分配给某个玩家就是：更新这个玩家开始被服务的时间；更新这个桌子开始为这个玩家服务后，结束服务的时间

	void AssignTableForPlayer(int t_id, int p_id) {
    // 玩家来的时候，这个桌子已空闲，玩家可以直接开始玩
    if (table[t_id].end_time <= player[p_id].arrive_time) {
        player[p_id].start_time = player[p_id].arrive_time;
    } else {
        // 玩家来的时候这个桌子还在服务上一个人，需要等它当前服务结束
        // 所以玩家开始玩的时间应该是这个桌子当前服务结束的时间
        player[p_id].start_time = table[t_id].end_time;
    }
    // 开始新的服务，更新这个桌子当前服务的结束时间
    table[t_id].end_time = player[p_id].start_time + player[p_id].play_time;
    // 这个桌子的服务人数增加
    table[t_id].serve_count++;
}

1. 找到这个玩家后面第一个vip的详细过程是什么？

   多说无益，直接看代码

	int FindNextVipPlayer(int p_id) {
	    p_id++;
	    while (p_id < player.size()) {
	        if (player[p_id].isvip)
	            return p_id;
	        p_id++;
	    }
	    // 不存在就返回-1
	    return -1;
	}

1. 不是说两个问题吗？哪来的3呢？是两个问题，但是第2个问题有一个大坑啊

   假如说这个队伍是这样的：1 2 3 4 v1 5 v2

   那我问你，处理 1号时找到他后面第一个vip是v1，v1优先被服务了，处理2号时，他后面第一个vip还是v1，难道再给v1服务一次？？不可能嘛，

   现实生活中，一个人被服务后就离开了，但我们这是个数组啊，除非你把那个位置数据删了，否则他就在那，但是你如果删了那不是要数组元素顺序后移或者前移？这浪费的时间可就多了，而且很可能因为粗心大意导致数组越界访问。

   所以我另外创建了一个bool served[10000]，初始化为false，当某个vip被服务后就把对应位置置为true，避免被重复选取。所以我 FindNextVipPlayer 也就变成了这样：

	int FindNextVipPlayer(int p_id) {
	    p_id++;
	    while (p_id < player.size()) {
	        // 是会员！且未被服务！
	        if (player[p_id].isvip && !served[p_id])
	            return p_id;
	        p_id++;
	    }
	    return -1;
	}

同时，在上面 四种分类讨论 中，对于碰到的vip玩家，也要加上是不是已经服务过的判断，如果是就直接跳过它服务下一个人。这一点我在代码注释里写的很详细，大家自己看吧。

满分代码

这注释你要是还看不明白，尽管来打死我！！！！

#include <algorithm>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

// 俱乐部开门时间，以 s 为单位
int club_open_time = 3600 * 8;
// 俱乐部关门时间，以 s 为单位
int club_close_time = 3600 * 21;

// 玩家
struct Player {
    // 到达时间，开始时间，玩耍时间
    int arrive_time, start_time, play_time;
    bool isvip; // 是否是 vip
};
// 桌子
struct Table {
    // 当前服务结束时间，已服务玩家个数
    // 刚开始全是8:00开始服务
    int end_time = club_open_time, serve_count;
    bool isvip; // 是否是为vip预留的桌子
};

// 保存玩家，和 桌子
vector<Player> player;
vector<Table> table;

// 比较某个vip是否已经被服务过了
bool served[10000];

// 按到达的先后顺序排队
bool cmp1(Player a, Player b) { return a.arrive_time < b.arrive_time; }
// 输出时，按被服务时间排序
bool cmp2(Player a, Player b) { return a.start_time < b.start_time; }

// 将某个桌子提供给某个玩家
void AssignTableForPlayer(int t_id, int p_id) {
    // 玩家来的时候，这个桌子已空闲，玩家可以直接开始玩
    if (table[t_id].end_time <= player[p_id].arrive_time) {
        player[p_id].start_time = player[p_id].arrive_time;
    } else {
        // 玩家来的时候这个桌子还在服务上一个人，需要等它当前服务结束
        // 所以玩家开始玩的时间应该是这个桌子当前服务结束的时间
        player[p_id].start_time = table[t_id].end_time;
    }
    // 开始新的服务，更新这个桌子当前服务的结束时间
    table[t_id].end_time = player[p_id].start_time + player[p_id].play_time;
    // 这个桌子的服务人数增加
    table[t_id].serve_count++;
}

// 找到这个人后面第一个会员未被服务的会员，被服务过了就跳过，如果不存在就返回-1
int FindNextVipPlayer(int p_id) {
    p_id++;
    while (p_id < player.size()) {
        // 是会员！且未被服务！
        if (player[p_id].isvip && !served[p_id])
            return p_id;
        p_id++;
    }
    return -1;
}

int main() {
    // n个玩家，k个桌子，m个vip桌子
    int n, k, m;
    cin >> n;
    Player p;
    int hh, mm, ss, t, flag;
    while (n-- > 0) {
        scanf("%d:%d:%d %d %d", &hh, &mm, &ss, &t, &flag);
        int arrive = hh * 3600 + mm * 60 + ss;
        // 玩家来的时候俱乐部关门，不用管他了
        if (arrive >= club_close_time)
            continue;
        p.arrive_time = arrive;
        // 一个玩家最多玩2小时
        t = t * 60;
        if (t > 7200)
            t = 7200;
        p.play_time = t;
        // 是否是vip
        p.isvip = flag == 1 ? true : false;
        // 把玩家被服务时间初始化为俱乐部关门时间，便于最后输出时淘汰掉哪些未被服务的玩家
        p.start_time = club_close_time;
        // 保存当前玩家
        player.push_back(p);
    }
    cin >> k >> m;
    // 桌子从1到K编号
    table.resize(k + 1);
    // 读入m个vip桌子序号
    int t_id;
    while (m-- > 0) {
        cin >> t_id;
        table[t_id].isvip = true;
    }
    // 玩家按到达时间排队
    sort(player.begin(), player.end(), cmp1);
    int i = 0;
    // 逐个处理玩家
    while (i < player.size()) {
        // 找到第一个结束服务的桌子
        int index = -1, min_end = INT_MAX;
        for (int j = 1; j <= k; ++j) {
            if (table[j].end_time < min_end) {
                index = j;
                min_end = table[j].end_time;
            }
        }
        // 最早结束的桌子结束当前服务都要等到俱乐部关门了，顾客可以全回家了，没戏了
        if (table[index].end_time >= club_close_time)
            break;
        // 这个桌子是给会员留的
        if (table[index].isvip) {
            // 这个人也是会员
            if (player[i].isvip) {
                // 并且没被服务过，就直接分配给他，
                if (!served[i]) {
                    AssignTableForPlayer(index, i);
                    // 标记这个会员被服务
                    served[i] = true;
                    // 然后处理下一个人，所以 i++
                    i++;
                } else {
                    // 服务过了就直接下一个
                    i++;
                }
            // 他是普通人
            } else {
                // 找到他后面第一个vip
                // 如果不存在，或者 存在，但是当前桌子结束服务的时候这个vip还没来，
                // 他才可以用这个桌子，
                int vip = FindNextVipPlayer(i);
                if (vip == -1 || player[vip].arrive_time > table[index].end_time) {
                    AssignTableForPlayer(index, i);
                    // 然后处理下一个人，所以 i++
                    i++;
                } else {
                    // 他后面有会员，而且这个会员的到达时间在这个桌子结束服务之前，
                    // 这个桌子就给会员用
                    AssignTableForPlayer(index, vip);
                    // 标记这个会员被服务
                    served[vip] = true;
                    // 相当于这个人被插队了，下一个还是处理他，所以 i不变
                }
            }
        // 普通桌子
        } else {
            // 这个人是普通人就分配给他，
            if (!player[i].isvip) {
                AssignTableForPlayer(index, i);
                // 然后处理下一个人，所以 i++
                i++;
            // 这个人是会员，并且没被服务过，
            } else if (!served[i]) {
                // 先看所有给会员预留的桌子是否有空闲，有就给他，没有就把这个普通桌子给他
                // 找到所有会员桌中最早结束的那个
                int t_vip = -1, t_vip_min_end = INT_MAX;
                for (int j = 1; j <= k; ++j) {
                    if (table[j].isvip && table[j].end_time < t_vip_min_end) {
                        t_vip = j;
                        t_vip_min_end = table[j].end_time;
                    }
                }
                // 最早结束的会员桌在他来之前服务完了，说明有可用的会员桌，分配给他
                if (t_vip != -1 && table[t_vip].end_time <= player[i].arrive_time) {
                    AssignTableForPlayer(t_vip, i);
                    // 标记这个会员被服务
                    served[i] = true;
                    // 然后处理下一个人，所以 i++
                    i++;
                } else {
                    // 没有可用的会员桌，就把当前这个普通桌子给他
                    AssignTableForPlayer(index, i);
                    // 标记这个会员被服务
                    served[i] = true;
                    // 然后处理下一个人，所以 i++
                    i++;
                }
            // 这个人是会员但是被服务过了就直接处理下一个
            } else {
                i++;
            }
        }
    }
    // 处理完所有玩家，按照被服务的开始时间排序
    sort(player.begin(), player.end(), cmp2);
    // 输出结果，无法被服务的自动排除
    for (auto it : player) {
        if (it.start_time >= club_close_time)
            continue;
        // 到达时间
        printf("%02d:%02d:%02d ", it.arrive_time / 3600,
               it.arrive_time % 3600 / 60, it.arrive_time % 60);
        // 被服务时间
        printf("%02d:%02d:%02d ", it.start_time / 3600,
               it.start_time % 3600 / 60, it.start_time % 60);
        // 等待时间
        printf("%.0f\n", round((it.start_time - it.arrive_time) / 60.0));
    }
    // 每个桌子服务了几个人
    printf("%d", table[1].serve_count);
    for (int i = 2; i <= k; ++i)
        printf(" %d", table[i].serve_count);

    return 0;
}

说实在的，这个题，只要分类讨论细节想到位了，真的不难！想不到位就多想想呗，把我这个博客多看几遍你绝对明白！啊哈哈哈！