배분 문제!

Greedy 사고

빠른 거랑 느린 거랑 있을 때,

• 느린 게 먼저 끝나면 기다리는 시간+빠른거 소요시간 vs. 느린거 소요시간 비교해서 작은 걸로 선택
• 빠른 게 먼저 끝나면 빠른거 소요시간 vs. 느린거 소요시간+기다리는 시간인데, 무조건 빠른거 고름

3개 있을 때, 한 심사대 끝나면 그거보다 소요시간 작은 것들+기다리는 시간 vs. 방금 끝난거 소요시간 비교해서 가장 작은 거부터 넣음.

근데 남은 사람 수 ≥ 소요시간 작은 것들 개수+1이면 방금 끝난 거에 고민 없이 사람 투입.

사람 넣느냐 마느냐 판단 기준: 심사대 소요시간 + 남은 시간

정리

남은 사람 ≥ 심사대 수이면 웨이팅 없이 즉시 투입.

남은 사람 < 심사대 수이면 남은시간+소요시간 작은 순서대로

min ∑a_iy_i s.t. ∑x_i = n ∑a_iy_i ≥ a_i*x_i for 1≤i≤n y_i ≤ x_i for 1≤i≤n x_i, y_i ≥ 0 x_i, y_i is integer

이분탐색 적용

min(times)이상 max(times) * n이하에서 탐색

mid = 총 시간

mid/n = 인당 평균 소요시간