PAT -- 甲级1014 (1014 Waiting in Line）

1014 Waiting in Line (30 分)

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 $(N M + 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, $customer_1$ is served at $window_1$ while $customer_2$ is served at $window_2$ . $Customer_3$ will wait in front of $window_1$ and $customer_4$ will wait in front of $window_2$ . $Customer_5$ will wait behind the yellow line.

At 08:01, $customer_1$ is done and $customer_5$ enters the line in front of $window_1$ since that line seems shorter now. $Customer_2$ will leave at 08:02, $customer_4$ at 08:06, $customer_3$ at 08:07, and finally $customer_5$ at 08:10.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 4 positive integers: $N$ ( $≤20\le 20$ , number of windows), $M$ ( $≤10\le 10$ , the maximum capacity of each line inside the yellow line), $K$ ( $≤1000\le 1000$ , number of customers), and $Q$ ( $≤1000\le 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 Specification:

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，q分别代表n个窗口，每个窗口的队列容量为m，有k个任务依次选择窗口处理事件，以及q组查询。接下来一行k个数字代表k个任务对应的占据窗口的时间。再一行的q个查询表示第i个任务的任务处理结束时间。

时间规则如下：n个窗口从8:00开放到17:00，也就是说过了17:00就不会有新的任务开启执行，但超过这个时间但仍未结束的任务会继续执行直到完成，单个任务的执行分钟数小于1000，所以不会隔天才完成！

选择窗口的算法如下，如果一些任务同时执行完毕，新的任务要开始运行并且此刻有多个窗口有空余位置，那么这个任务会优先选择排队少的，如果多个相同少的窗口优先选择序号小的窗口

思路：…模拟题，不是很好搞，代码写得有点长。推荐柳神的本题做法柳神大法。至于我的思路是这样的：

用一个队列维护未处理的进程tab
用n个双端队列/链表维护每个窗口的就绪进程，并且存的是各个进程的结束运行时间和其对应的下标的一个pair
用一个小根堆维护当前n个窗口即将执行的op个进程(op <= n)，优化和查找的复杂度 $O (l o g n)$
然后先预处理一下把 $n * m$ 个进程按规则加入各个窗口队列，接着根据小根堆每次弹出一个最小的即将执行的进程执行（出队），并且如果未处理的进程队列还有进程的话就加入该窗口就绪队列。这里如果结束分钟大于540的话说明会超过17：00，标记为-1，将来查询到-1时输入Sorry。

Ps：其实这个模拟过程类似于计算机操作系统中SJF调度算法（短作业优先调度算法)。多个窗口就像多个调度就绪队列

Code：

#include <stdio.h>
#include <utility>
#include <queue>
#include <deque>
#include <string.h>

using namespace std;
const int maxn = (int)1e3+5;

struct myCompare {
  bool operator () (const pair<int, int> A, const pair<int, int> B) {
    if (A.first == B.first) return A.second > B.second;
    return A.first > B.first;
  }
};

priority_queue<pair<int, int >, vector<pair<int, int > >, myCompare> pq; //pi --> time id
deque<pair<int, int > > window[maxn];
queue<pair<int, int > > tab;
int n,m,k,q; //n个窗口 m个队列长度 k个人 q个询问
int val[maxn], qry[maxn], ans[maxn];
pair<int, int> tmp, op, fresh;

void Init() {
  while (!pq.empty()) {
    pq.pop();
  }
  for (int i = 0; i < k; i++) {
    window[i].clear();
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (tab.empty()) break;
      tmp = tab.front();
      tab.pop();
      if (!window[j].empty()) {
          if (window[j].back().first >= 540) ans[tmp.second] = -1;  //开始的时间超过下午5点就标记一下(-1)
          tmp.first += window[j].back().first;                      //以上次结束的时间为开始时间
      } else {
          pq.push(make_pair(tmp.first, j));                     //第一排处理结束时间的窗口小根堆
      }
      window[j].push_back(tmp);
    }
  }
}

void Solve() {
  while (!pq.empty()) {
    tmp = pq.top();
    pq.pop();
    op = window[tmp.second].front(); //拿出该窗口的第一个
// printf("window = %d value = %d\n", tmp.second, op.first);
    //寻找新的进程加入该窗口的就绪队列中 注意：为防止该窗口只有一个进程，顺序应该时先加后减！
    if (!tab.empty()) {
      fresh = tab.front();
      tab.pop();
      if (window[tmp.second].back().first >= 540) ans[fresh.second] = -1;  //开始的时间超过下午5点就标记一下(-1)
      fresh.first += window[tmp.second].back().first;
      window[tmp.second].pop_front();  //第一个运行结束
      window[tmp.second].push_back(fresh);
      pq.push(make_pair(window[tmp.second].front().first, tmp.second));  //把新的第一排的信息加入小根堆中
    } else {
      window[tmp.second].pop_front();  //第一个运行结束
      if (!window[tmp.second].empty()) {  //这个窗口还有进程
        pq.push(make_pair(window[tmp.second].front().first, tmp.second));  //把新的第一排的信息加入小根堆中
      }
    }
    if (ans[op.second] == -1) continue; //开始时间超过下午5点
    ans[op.second] = op.first; //结束时间
  }
}

int main() {
  int hour,minute;
  while (!tab.empty()) {
    tab.pop();
  }
  scanf("%d%d%d%d", &n, &m, &k, &q);
  for (int i = 0; i < k; i++) {
    scanf("%d", &val[i]);
    tab.push(make_pair(val[i], i)); //处理的值
  }
  for (int i = 0; i < q; i++) {
    scanf("%d", &qry[i]);
  }
  memset(ans, 0, sizeof(ans));
  Init();  //预处理
  Solve(); //动态模拟多窗口
  for (int i = 0; i < q; i++) {
    if (ans[qry[i]-1] == -1) printf("Sorry\n");
    else {
      hour = ans[qry[i]-1] / 60 + 8;
      minute = ans[qry[i]-1] % 60;
      printf("%02d:%02d\n", hour, minute);
    }
  }
  return 0;
}