19594번 - 슈퍼 컴퓨터 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 256 MB | 116 | 51 | 42 | 45.161% |
문제
당신은 슈퍼 컴퓨터에서 총 N개의 프로그램을 순차적으로 실행하여 실험을 해야한다.
편의상 프로그램은 1번부터 N번까지 번호가 매겨져 있으며 i번 프로그램은 총 H[i]시간 동안 실행되며 이 프로그램의 희망 데드라인은 지금부터 D[i]시간 후다.
N개의 프로그램이 있으므로 실행하는 순서는 총 N! 가지가 가능하다.
i번 프로그램이 끝나는 시각을 지금부터 C[i] 시간 후 라고 하자. 편의상 max(0, C[i] - D[i]) 를 i번 프로그램의 "지각도" 라고 칭하자 (희망 데드라인보다 늦게 끝나지 않은 경우엔 지각도가 0이다).
"최대 지각도"는 N개 프로그램의 지각도 중 최대값으로 정의한다.
그런데 이 슈퍼 컴퓨터에는 특이한 기능이 있는데, N개의 프로그램 중 딱 하나의 프로그램을 (당신이) "최우선 처리 대상"으로 지정하여 해당 프로그램은 무조건 1시간만에 실행되도록 할 수 있다.
예를 들어 N = 3, H = [2, 4, 6], D = [3, 5, 8]이라 하자.
이 경우, 1번부터 3번 프로그램까지 순서대로 실행을 하고 3번 프로그램 실행시간을 1시간이 되도록 지정했다면,
1번 프로그램은 지금부터 시작하여 2시간 후에 끝나며 (C[1] = 2), 2번은 그로부터 4시간 후에 끝나고 (C[2] = 6), 3번은 그로부터 1시간 후에 끝나서 C[3] = 7이 된다.
이 때 각 프로그램의 지각도는 0, 1, 0이며, 이 중 최대값이 1이므로 최대 지각도는 1이다.
같은 예제에서 3번 프로그램부터 1번 프로그램까지 역순으로 실행하고, 3번 프로그램의 실행시간을 1시간이 되도록 지정했다면,
3번 프로그램은 지금부터 시작하여 1시간 후에 끝나며 (C[3] = 1), 2번은 그로부터 4시간 후 (C[2] = 5), 1번은 그로부터 2시간 후에 끝나서 C[1] = 7이 된다.
이 때 각 프로그램의 지각도는 4, 0, 0이며, 이 중 최대값이 4이므로 최대 지각도는 4이다.
이 예제의 경우, 첫 번째 방법이 최대 지각도를 최소화 하는 방법이다.
입력으로 N개의 프로그램의 실행시간과 희망 데드라인이 주어졌을 때, 달성 가능한 최대 지각도의 최소값을 구하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스크 케이스는 세 줄에 걸쳐 주어지는데, 그 중 첫 줄에 프로그램의 수 N이 주어진다.
둘째 줄에 N개의 정수가 공백으로 구분되어 주어지며, 실행시간 H[i]를 나타낸다.
셋째 줄에 N개의 정수가 공백으로 구분되어 주어지며, 희망 데드라인 D[i]를 나타낸다.
출력
각 테스트 케이스에 대해 달성 가능한 최대 지각도의 최소값을 출력한다.
제한
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 100,000
- 1 ≤ H[i], D[i] ≤ 1,000
예제 입력 1
4 3 2 4 6 3 5 8 3 4 9 1 10 9 20 3 4 3 5 2 1 3 5 8 1 2 6 2 8 9 6 2 1
예제 출력 1
1 0 5 5
시간 제한
- Java 8: 3 초
- Python 3: 2 초
- PyPy3: 2 초
- Java 8 (OpenJDK): 3 초
- Java 11: 3 초
- Python 2: 2 초
- PyPy2: 2 초
- Kotlin (JVM): 3 초
- Java 15: 3 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호