50084. Machines and Jobs
難度：3/51
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
static inline int max(int a, int b){
return (a > b) ? a : b;
}
static inline int min(int a, int b){
return (a < b) ? a : b;
}
typedef struct{
int free_time;
int num_task;
int task_id[512];
int task_time[512];
int now_task;
} s_job;
int n, m;
s_job job[512] = {0};
int mchn_ready[512] = {0};
int get_time(s_job* j){
int mach_id = j->task_id[j->now_task];
int mach_time = j->task_time[j->now_task];
return max(j->free_time, mchn_ready[mach_id]) + mach_time;
}
void progress(s_job* j){
int mach_id = j->task_id[j->now_task];
int mach_time = j->task_time[j->now_task];
j->free_time = max(j->free_time, mchn_ready[mach_id]) + mach_time;
mchn_ready[mach_id] = j->free_time;
j->now_task++;
}
int main(){
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++){
scanf("%d %d", &job[i].free_time, &job[i].num_task);
for(int j = 0; j < job[i].num_task; j++){
scanf("%d %d", &job[i].task_id[j], &job[i].task_time[j]);
job[i].now_task = 0;
}
}
while(1){
int min_job_idx = -1, min_job_time = INT_MAX;
for(int i = 0; i < m; i++){
if(job[i].now_task == job[i].num_task) continue;
int this_time = get_time(&job[i]);
if(min_job_time > this_time){
min_job_idx = i;
min_job_time = this_time;
}
}
if(min_job_idx != -1) progress(&job[min_job_idx]);
else break;
}
for(int i = 0; i < m; i++){
printf("%d\n", job[i].free_time);
}
}