1014 Waiting in Line
第一次做模拟题。其实不难。
但耗了好久才30/30，可能这是第一个死磕自己的答案一天以上没AC，也没照着大佬代码最后AC掉的题（虽然看了大佬的思路23333）
说说我自己挖坑再爬出来的过程：
沉迷小说 两天多只a了这题qaq
这题的思路：
-
对前
n_win * m_len的customer（序号：i）排到第I mod m_len队尾
⚠️ 若该队前面一人的end_time已经>=OFF，那此人还是排在这一 队里，只不过包括他在内的应该排在这队的人都注定sorry啦，没必 要再算开始结束时间，直接continue。
一开始想成了break，测试点4就WA了。 -
对
n_win * m_len + 1开始的customer（序号：i）之前的
n_win * m_len占满了所有的队，因此选择最短的队（同样短则取序号小的队）就是选择最先有人出去的队。
#include <cstdio>
#include <queue>
using namespace std;
const int NW = 20, NK = 1010, OFF = 9 * 60, INF = 0x3F3F3F3F;
int n_win, m_len, k_cus, q_query;
struct Transaction {
int st_time;
int len;
int ed_time;
} transactions[NK];
queue<int> mq[NW];//end_time
int main() {
scanf("%d%d%d%d", &n_win, &m_len, &k_cus, &q_query);
for (int i = 0; i < k_cus; ++i) {
scanf("%d", &transactions[i].len);
transactions[i].st_time = INF;
transactions[i].ed_time = INF;
}
int i;
for (i = 0; i < n_win && i < k_cus; i++) {
transactions[i].st_time = 0;
transactions[i].ed_time = transactions[i].len;
mq[i].push(transactions[i].ed_time);
}
for (; i < n_win * m_len && i < k_cus; ++i) {
int j = i % n_win;
int t = mq[j].back();
if (t >= OFF)
continue;
transactions[i].st_time = t;
t += transactions[i].len;
transactions[i].ed_time = t;
mq[j].push(t);
}
for (; i < k_cus; ++i) {
int earlier = OFF, ind = -1;
for (int j = 0; j < n_win; j++) {
if (mq[j].front() < earlier) {
earlier = mq[j].front();
ind = j;
}
}
if (earlier < OFF) {
mq[ind].pop();
int t = mq[ind].back() + transactions[i].len;
transactions[i].st_time = mq[ind].back();
transactions[i].ed_time = t;
mq[ind].push(t);
}
}
int q, qr;
for (int j = 0; j < q_query; j++) {
scanf("%d", &q);
qr = transactions[q - 1].ed_time;
if (qr != INF && transactions[q - 1].st_time < OFF)
printf("%02d:%02d\n", (8 + qr / 60) % 24, qr % 60);
else puts("Sorry");
}
return 0;
}
之后考虑看看各位大佬的做法。。
