(繁)
题目大意
有若干乒乓球桌（编号1到N）和最多能玩2小时的玩家，若空闲则到达的人选择编号最小的乒乓球桌，若桌被占满了则排队。有VIP玩家和VIP球桌，若VIP球桌有空，则排在最前面的VIP玩家上桌，若没有VIP，则队首普通玩家上桌。轮到VIP玩家时，不是VIP桌也会上桌。8点到21点开业。
现给出每个人到达的时间、占桌时长（min）、是否VIP，以及桌子总数和VIP桌子数，VIP桌子编号。按照服务时间先后顺序输出每个人到达时间、得到服务时间、等待时长（以分钟单位取整），每桌服务人数。注意：如果这个人在得到服务时超过了21点，则不输出。
tips
1
e--计算结果 a--被除数 b--除数
1(四舍五入) ： e=(a+(b/2))/b
2(进一法) ： e=(a+(b-1))/b
2
vector容器的v.resize(int n,element)函数。
调整容器v大小为n；扩容后每个元素值为element，缺省为0。
坑
测试点4
如果输入的时长超过2小时的，要手动缩短成2小时。
测试点5、7
当有多个桌子空闲时，且空闲的里面有vip桌时，vip用户会选择编号最小的vip桌，即使有空闲的、编号更小的普通桌。如果空闲的里面没有vip桌，vip用户选择编号最小的桌。
测试点8
超时，不知道为啥
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>///////
#include<iostream>
using namespace std;
#define N 10000
#define K 102
#define CLOSE 21 * 60 * 60
struct people {
int arrive;
int serve;
int occupy;
bool vip;
}player[N + 1];
int tend[K];//该桌子当前最早结束使用时间
int Ptable[K] = { 0 };//记录每张桌子服务人数
int ifserve[N + 1] = { 0 };//标记该客户是否被服务, 0未服务，负数判断将不会服务
vector<people>pans;
void fenpei(int ren, int zhuo) {
player[ren].serve = tend[zhuo] < player[ren].arrive ? player[ren].arrive : tend[zhuo];
if (player[ren].serve < CLOSE) {
ifserve[ren] = 1;
pans.push_back(player[ren]);
tend[zhuo] = player[ren].serve + player[ren].occupy;
Ptable[zhuo]++;
}
}
//找到最早结束的桌子编号
int findmin(int a[], int k) {
int min = 1;
for (int i = 2;i <= k;i++) {
if (a[i] < a[min])
min = i;
}
return min;
}
//找到最早结束的VIP桌子编号
int findvipmin(int a[], int k, bool vip[]) {
int time = CLOSE + 2 * 60 * 60 + 1;
int min = -1;
for (int i = 1;i <= k;i++) {
if (vip[i] == 0)
continue;
if (a[i] < time) {
min = i;
time = a[i];
}
}
return min;
}
bool cmp_arrive(people a, people b) {
return a.arrive < b.arrive;
}
bool cmp_serve(people a, people b) {
return a.serve < b.serve;
}
int main() {
int n;
int k;//桌子数
int m;//vip桌子数
bool VIPtable[K] = { 0 };//是否为VIP桌子
int i, j;
//输入 剔除到达时间>=21点的
scanf("%d", &n);
for (i = 0;i < n;i++) {
int a, b, c;
scanf("%d:%d:%d", &a, &b, &c);
player[i].arrive = a * 60 * 60 + b * 60 + c;
int temptime;
scanf("%d%d", &temptime, &player[i].vip);
player[i].occupy = temptime > 120 ? 120 * 60 : temptime * 60;
if (player[i].arrive >= CLOSE) {
i--;
n--;
}
//player[i].wait = 0;
}
scanf("%d%d", &k, &m);
for (i = 1;i <= k;i++)
tend[i] = 8 * 60 * 60;
for (i = 0;i < m;i++) {
int temp;
scanf("%d", &temp);
VIPtable[temp] = 1;
}
sort(player, player + n, cmp_arrive);
//计算服务时间
for (i = 0;i < n;i++) {
if (ifserve[i] != 0)continue;//过滤掉提前处理的VIP
j = findmin(tend, k);//寻找最早结束编号最小的桌子
if (tend[j] > CLOSE)break;
//当第i个人来时，先判断是否是VIP
if (player[i].vip) {//是VIP
if (VIPtable[j]) fenpei(i, j); //桌是VIP桌，直接分配
else {//桌非VIP
if (tend[j] <= player[i].arrive) {//空桌不是VIP且人到时桌空，再找找有没有空VIP桌
int u = findvipmin(tend, k, VIPtable);
if (u > 0 && tend[u] <= player[i].arrive) {//若人到时VIP桌空，则分配
fenpei(i, u);
}
else fenpei(i, j);
}
else fenpei(i, j);
}
}
else {//队首不是VIP
if (VIPtable[j] && tend[j] > player[i].arrive) {
//桌是VIP桌且人要等，则看看后后面有没有VIP用户
int v = i;
for (;v < n;v++) {
if (player[v].vip)break;
}
if (v == n) fenpei(i, j);//后面没VIP了，队首普通用户上桌
else {
fenpei(v, j);//否则VIP插队
i--;//下一次循环还处理队首非VIP
}
}
else fenpei(i, j);
}
}
sort(pans.begin(), pans.end() , cmp_serve);
for (i = 0;i < pans.size();i++) {
int hh, mm, ss;
hh = pans[i].arrive / 3600;
mm = (pans[i].arrive - hh * 3600) / 60;
ss = pans[i].arrive - hh * 3600 - mm * 60;
printf("%02d:%02d:%02d ", hh, mm, ss);
hh = pans[i].serve / 3600;
mm = (pans[i].serve - hh * 3600) / 60;
ss = pans[i].serve - hh * 3600 - mm * 60;
printf("%02d:%02d:%02d ", hh, mm, ss);
//printf("***%d*** ", player[i].vip);
printf("%d
", (pans[i].serve - pans[i].arrive + 30) / 60);
}
for (i = 1;i <= k;i++) {
if (i != 1)printf(" ");
printf("%d", Ptable[i]);
}
return 0;
}
AC代码
参考了 (https://blog.csdn.net/a1552100455/article/details/100060101)
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
struct person {
int come, get, play, wait;
bool isvip = false;
}pperson;
struct table {
bool isvip = false;
int present = 8 * 3600;//当前该桌结束使用时间
int num = 0;
};
vector<person> vec, res;//res存放被服务的人
vector<table> tables;//角标就是编号
//所有人中最早到的VIP脚标
int getVIP(int index) {
index++;
while (index < vec.size() && vec[index].isvip == false) index++;
return index;
}
void alloac(int p, int t) {
vec[p].get = tables[t].present < vec[p].come ? vec[p].come : tables[t].present;
if (vec[p].get < 21 * 3600) {
res.push_back(vec[p]);
tables[t].num++;
tables[t].present = vec[p].get + vec[p].play;
}
}
bool cmp_come(person p1, person p2) {
return p1.come < p2.come;
}
bool cmp_get(person p1, person p2) {
return p1.get < p2.get;
}
int main() {
int n, k, p;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int hour, min, sec, play, flag;
scanf("%d:%d:%d %d %d", &hour, &min, &sec, &play, &flag);
pperson.come = hour * 3600 + min * 60 + sec;
pperson.get = 21 * 3600;
if (pperson.come >= 21 * 3600) continue;
pperson.play = play > 120 ? 120 * 60 : play * 60;
pperson.isvip = flag;
vec.push_back(pperson);
}
scanf("%d %d", &k, &p);
tables.resize(k + 1);
for (int i = 0; i < p; i++) {
int temp;
scanf("%d", &temp);
tables[temp].isvip = true;
}
sort(vec.begin(), vec.end(), cmp_come);
int i = 0;
int vipid = getVIP(-1);
while (i < vec.size()) {
int min = 999999999, index = -1;
for (int j = 1; j < tables.size(); j++) {
if (tables[j].present < min) {
min = tables[j].present;
index = j;
}
}//找最早结束的桌子index
if (tables[index].present >= 21 * 3600) break;
if (vec[i].isvip == true && i < vipid) {
i++;
continue;
}
if (tables[index].isvip == true) {//会员桌子
//先检查会员 插队
if (vec[i].isvip == true) {//队头就是会员
alloac(i, index);
vipid = getVIP(vipid);
i++;
}
else {
if (vipid < vec.size() && vec[vipid].come <= tables[index].present) {//看看队里有没有会员
alloac(vipid, index);
vipid = getVIP(vipid);
}
else {//没有会员
alloac(i, index);
i++;
}
}
}
else {//普通桌子
int mintemp = 999999999; int tempindex = -1;
if (vec[i].isvip == true) {//第一个人是VIP
for (int k = 1; k < tables.size(); k++) {
if (tables[k].isvip && tables[k].present < mintemp) {
mintemp = tables[k].present;
tempindex = k;
}
}
if (tempindex != -1 && tables[tempindex].present <= vec[i].come) {//有会员桌子 插队
alloac(i, tempindex);
vipid = getVIP(vipid);
i++;
}
else {//没有会员桌子 那就跟普通人一样
alloac(i, index);
vipid = getVIP(vipid);
i++;
}
}
else {//普通人
alloac(i, index);
i++;
}
}
}
sort(res.begin(), res.end(), cmp_get);
for (int i = 0; i < res.size(); i++) {
printf("%02d:%02d:%02d ", res[i].come / 3600, res[i].come % 3600 / 60, res[i].come % 60);
printf("%02d:%02d:%02d %.0f
", res[i].get / 3600, res[i].get % 3600 / 60, res[i].get % 60, round((res[i].get - res[i].come) / 60.0));
}
printf("%d", tables[1].num);
for (int i = 2; i < tables.size(); i++)
printf(" %d", tables[i].num);
return 0;
}
仔细比对了自己写的代码，比了好久都不知道复杂在了哪......如果有好心的大佬帮忙解答一下，感激不尽。
在我看来我们的区别是我是先看第一个人再看第一张桌，AC代码是先看桌再看人。