6066 : 작업 스케줄링 (최소 대기)
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
작업 스케줄링 (SJF)
N개의 작업이 각각 요청 시점 $A_i$와 소요 시간 $D_i$를 가집니다.
SJF(Shortest Job First) 스케줄링으로 평균 대기 시간을 최소화하시오.
규칙:
- 한 번에 하나의 작업만 처리합니다.
- 처리 가능한 작업(현재 시간 이전에 요청된) 중 소요 시간이 가장 짧은 작업을 먼저 처리합니다.
- 대기 시간 = 처리 시작 시각 - 요청 시각
출력: 평균 대기 시간을 소수점 둘째 자리까지 반올림하여 출력합니다.
[제약 조건]
• 작업 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 작업 도착 시간: $0 \le t \le 10^9$ (정수)
• 작업 처리 시간: $1 \le p \le 10^4$ (정수)
N개의 작업이 각각 요청 시점 $A_i$와 소요 시간 $D_i$를 가집니다.
SJF(Shortest Job First) 스케줄링으로 평균 대기 시간을 최소화하시오.
규칙:
- 한 번에 하나의 작업만 처리합니다.
- 처리 가능한 작업(현재 시간 이전에 요청된) 중 소요 시간이 가장 짧은 작업을 먼저 처리합니다.
- 대기 시간 = 처리 시작 시각 - 요청 시각
출력: 평균 대기 시간을 소수점 둘째 자리까지 반올림하여 출력합니다.
[제약 조건]
• 작업 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 작업 도착 시간: $0 \le t \le 10^9$ (정수)
• 작업 처리 시간: $1 \le p \le 10^4$ (정수)
입력 설명
첫째 줄에 작업의 개수 N (1 ≤ N ≤ 10,000)이 주어집니다.
둘째 줄부터 N개의 줄에 각 작업의 요청 시점 A_i와 소요 시간 D_i가 주어집니다.
둘째 줄부터 N개의 줄에 각 작업의 요청 시점 A_i와 소요 시간 D_i가 주어집니다.
출력 설명
평균 대기 시간을 소수점 둘째 자리까지 반올림하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
0 3
1 9
2 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3.67