#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
const int N = 10010, M = 110, INF = 1000000;
int n, k, m;
struct Person // 球员
{
int arrive_time, play_time;
int start_time, waiting_time;
bool operator< (const Person& t) const // sort排序
{
if (start_time != t.start_time) return start_time < t.start_time;
return arrive_time < t.arrive_time;
}
bool operator> (const Person& t) const // 优先队列中比较大小, 优先队列优先使用这个?
{
return arrive_time > t.arrive_time;
}
};
struct Table // 球桌
{
int id;
int end_time;
bool operator> (const Table& t) const // 优先队列中比较大小
{
if (end_time != t.end_time) return end_time > t.end_time;
return id > t.id;
}
};
bool is_vip_table[M]; // 用来记录是否是vip 球桌
int table_cnt[M]; // 总共的球桌数量
vector<Person> persons; // 总共的球员数量
void assign(priority_queue<Person, vector<Person>, greater<Person>>& ps, // 注意选用引用类型
priority_queue<Table, vector<Table>, greater<Table>>& ts)
{
auto p = ps.top(); ps.pop();
auto t = ts.top(); ts.pop();
p.waiting_time = round((t.end_time - p.arrive_time) / 60.0); // c++ 四舍五入方案
p.start_time = t.end_time;
table_cnt[t.id] ++ ; // 输出桌子信息
persons.push_back(p); // 结果玩耍的人员集合
ts.push({t.id, t.end_time + p.play_time});// 更新最大堆
}
string get_time(int secs)
{
char str[20]; // 字符串写入方案
sprintf(str, "%02d:%02d:%02d", secs / 3600, secs % 3600 / 60, secs % 60);
return str;
}
int main()
{
cin >> n;
// 设置 普通成员堆 和 vip堆
priority_queue<Person, vector<Person>, greater<Person>> normal_persons;
priority_queue<Person, vector<Person>, greater<Person>> vip_persons;
// 设置哨兵元素 , 这样就不会为空 ,方便运算的实现
normal_persons.push({INF});
vip_persons.push({INF});
// 读取数据
for (int i = 0; i < n; i ++ )
{
int hour, minute, second;
int play_time, is_vip;
// 时分秒与游戏时间 和 用户类型
scanf("%d:%d:%d %d %d", &hour, &minute, &second, &play_time, &is_vip);
// 与0:00 进行比较 精确到秒
int secs = hour * 3600 + minute * 60 + second;
play_time = min(play_time, 120);
play_time *= 60;
// 分类塞入
if (is_vip) vip_persons.push({secs, play_time});
else normal_persons.push({secs, play_time});
}
priority_queue<Table, vector<Table>, greater<Table>> normal_tables;
priority_queue<Table, vector<Table>, greater<Table>> vip_tables;
normal_tables.push({-1, INF});
vip_tables.push({-1, INF});
cin >> k >> m;
for (int i = 0; i < m; i ++ )
{
int id;
cin >> id;
is_vip_table[id] = true;
}
for (int i = 1; i <= k; i ++ ) // 初始化 开始服务时间
if (is_vip_table[i]) vip_tables.push({i, 8 * 3600});
else normal_tables.push({i, 8 * 3600});
while (normal_persons.size() > 1 || vip_persons.size() > 1) // 接下来再开始处理人
{
// 模拟队列
auto np = normal_persons.top();
auto vp = vip_persons.top();
// 本来是用处理两种情况的 现在直接变成只处理一种
int arrive_time = min(np.arrive_time, vp.arrive_time);
/**
* 本来就是可以做成一种情况的来分析的
* 因为所有的来访选手都是按时间顺序进行排序
* 把 所有的桌子时间改成最早来的那个选手的时间, 不影响以后的判断
*
*/
while (normal_tables.top().end_time < arrive_time) // O(klogk)
{
auto t = normal_tables.top();
normal_tables.pop();
t.end_time = arrive_time;
normal_tables.push(t);
}
/**
* 同理,对于vip桌子也是一致的, 因为是按选手来顺序排序,并不需要特判用户类型
*
*
*/
while (vip_tables.top().end_time < arrive_time)
{
auto t = vip_tables.top();
vip_tables.pop();
t.end_time = arrive_time;
vip_tables.push(t);
}
auto nt = normal_tables.top();
auto vt = vip_tables.top();
// 获取最早结束的那张桌子
int end_time = min(nt.end_time, vt.end_time);
//如果已经超过了服务时间了 则直接结束
if (end_time >= 21 * 3600) break;
// 先考虑vip同学, 如果他到达的时间 比桌子结束时间短 并且是vip的桌子有空座,则把vip分配给那个
if (vp.arrive_time <= end_time && vt.end_time == end_time) assign(vip_persons, vip_tables);
else if (np.arrive_time < vp.arrive_time)// 如果是普通成员先来
{
// 并且普通桌子的结束时间比vip桌子的结束时间快
if (nt > vt) assign(normal_persons, vip_tables); //
else assign(normal_persons, normal_tables);
}
else // 这种情况就是vip同学 到达的时间比普通成员来的早,但没有vip桌子空余
{
// 如果最后还是vip 桌子结束的快
if (nt > vt) assign(vip_persons, vip_tables);
else assign(vip_persons, normal_tables);
}
}
sort(persons.begin(), persons.end());
for (auto person : persons)
{
cout << get_time(person.arrive_time) << ' ' << get_time(person.start_time) << ' ';
cout << person.waiting_time << endl;
}
cout << table_cnt[1];
for (int i = 2; i <= k; i ++ ) cout << ' ' << table_cnt[i];
cout << endl;
return 0;
}
写的真好