1401 : Registration Day
Description
It's H University's Registration Day for new students. There are M offices in H University, numbered from 1 to M. Students need to visit some of them in a certain order to finish their registration procedures. The offices are in different places. So it takes K units of time to move from one office to another.
There is only one teacher in each office. It takes him/her some time to finish one student's procedure. For different students this time may vary. At the same time the teacher can only serve one student so some students may need to wait outside until the teacher is available. Students who arrived at the office earlier will be served earlier. If multiple students arrived at the same time they will be served in ascending order bystudent number.
N new students need to finish his/her registration. They are numbered from 1 to N. The ith student's student number is Si. He will be arrived at H University's gate at time Ti. He needs to visit Pi offices in sequence which are Oi,1, Oi,2, ... Oi,Pi. It takes him Wi,1, Wi,2, ... Wi,Pi units of time to finish the procedure in respective offices. It also takes him K units of time to move from the gate to the first office.
For each student can you tell when his registration will be finished?
Input
The first line contains 3 integers, N, M and K. (1 <= N <= 10000, 1 <= M <= 100, 1 <= K <= 1000)
The following N lines each describe a student.
For each line the first three integers are Si, Ti and Pi. Then following Pi pairs of integers: Oi,1, Wi,1, Oi,2, Wi,2, ... Oi,Pi, Wi,Pi. (1 <= Si <= 2000000000, 1 <= Ti <= 10000, 1 <= Pi <= M, 1 <= Oi,j <= M, 1 <= Wi,j <= 1000)
Output
For each student output the time when he finished the registration.
Sample Hint
Student 1600012345 will be arrived at the gate at time 500. He needs to first visit Office #1 and then Office #2. He will be arrived at office #1 at time 600. He will leave office #1 at time 1100. Then He will arrive at office #2 at 1200. At the same time another student arrives at the same office too. His student number is smaller so he will be served first. He leaves Office #2 at 1700. End of registration.
Student 1600054321 will be arrived at the gate at time 1100. He will be arrived at Office #2 at 1200. Another student with smaller student number will be served first so he waits for his turn until 1700. He leaves Office #2 at 2000. End of registration.
Sample Input
2 2 100
1600012345 500 2 1 500 2 500
1600054321 1100 1 2 300
Sample Output
1700
2000
思路分析
这题的关键有两点，一是对时间的认识和表示，二是使用优先队列这个数据结构。
解题的思路是这样的，每个学生都对应一个他所处的时间点，所有学生按时间点组成优先队列（时间点相同则按学号升序排列）。每个office对应一个它available的时间点。模拟注册的过程如下：取优先队列的头元素，他对应的时间点是所有学生对应时间点中最靠前的，因此应该被先服务，我们查找他现在应该去那个office，计算他在此office注册完成的时间点，更新office的available时间，若该学生还有office要去，则更新他的信息并再次将他插入优先队列中，否则记录该学生的完成时间。直至优先队列为空，说明注册全部完成。
AC代码
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int time;
int index;
int s;
int t;
int p;
int* os;
int* ws;
int off = 0;
bool operator< (Node a) const {
if (time == a.time)
return s > a.s;
else
return time > a.time;
}
};
int main() {
priority_queue <Node> pq;
int office[100] = { 0 };
int total[10000];
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
Node tmp;
cin >> tmp.s >> tmp.t >> tmp.p;
tmp.index = i;
tmp.os = new int[tmp.p];
tmp.ws = new int[tmp.p];
for (int j = 0; j < tmp.p; j++) {
cin >> tmp.os[j] >> tmp.ws[j];
}
tmp.time = tmp.t + k;
pq.push(tmp);
}
while (!pq.empty()) {
Node s = pq.top();
pq.pop();
int off = s.os[s.off] - 1;
int et;
if (s.time >= office[off])
et = s.time + s.ws[s.off];
else
et = office[off] + s.ws[s.off];
office[off] = et;
s.time = et + k;
s.off++;
if (s.off < s.p)
pq.push(s);
else
total[s.index] = et;
}
for (int i = 0; i < n; i++)
cout << total[i] << endl;
return 0;
}
