32093번 - ジェットコースター 2
(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
JAG(Japan Amusement Group)는 많은 관광객들이 찾아오는 놀이공원으로, 그 중에서도 롤러코스터는 특히 인기가 좋은 어트랙션이다.
오늘도 대성황을 이루고 있는 JAG의 롤러코스터 앞에는 수많은 단체 손님들이 줄을 서서 차례를 기다리고 있다. 현재 대기열에는 N팀의 단체 손님이 있으며, 그 중 i번째 팀은 ai명으로 이루어져 있다.
롤러코스터는 한 번 운행할 때마다 최대 M명까지 탑승할 수 있으며, 당신은 놀이공원의 스태프로서 롤러코스터가 운행할 때마다 다음 규칙에 따라 손님을 탑승시킨다. 이 과정을 대기열에 손님이 남지 않을 때까지 반복한다.
JAG의 폐장 시간이 임박했기 때문에, 당신은 인접한 팀끼리 대기 순서를 최대 한 번 바꾸어서 롤러코스터의 운행 횟수를 줄일 수 없을지 고민하고 있다. 구체적으로 당신은 다음 동작을 최대 한 번 수행할 수 있다.
위의 동작을 최적으로 수행했을 때, 대기열의 모든 손님을 수용하는 데 필요한 롤러코스터 운행 횟수의 최솟값을 구하는 프로그램을 작성하여라. 대기열에 새로운 팀이 추가되거나 기존 팀이 대기열에서 벗어나는 경우는 생각하지 않는다.
입력은 50개 이하의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 다음과 같이 주어진다.
N M a1 a2 ... aN
첫째 줄에는 대기열에 있는 팀의 수 N과 롤러코스터의 정원 M이 주어진다. (2 ≤ N ≤ 2×105, 1 ≤ M ≤ 109)
둘째 줄에는 N개의 정수 a1, a2, ..., aN이 주어진다. 이때 ai는 대기열의 i번째 팀의 인원수이다. (1 ≤ ai ≤ M)
모든 테스트 케이스에 걸쳐 N의 합은 2×106 이하이다.
입력의 끝에는 0이 두 개 주어진다.
각 테스트 케이스마다 문제의 정답을 한 줄로 출력한다.
댓글을 작성하려면 로그인해야 합니다.
dlaud5379 9달 전 1
(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
문제
JAG(Japan Amusement Group)는 많은 관광객들이 찾아오는 놀이공원으로, 그 중에서도 롤러코스터는 특히 인기가 좋은 어트랙션이다.
오늘도 대성황을 이루고 있는 JAG의 롤러코스터 앞에는 수많은 단체 손님들이 줄을 서서 차례를 기다리고 있다. 현재 대기열에는 N팀의 단체 손님이 있으며, 그 중 i번째 팀은 ai명으로 이루어져 있다.
롤러코스터는 한 번 운행할 때마다 최대 M명까지 탑승할 수 있으며, 당신은 놀이공원의 스태프로서 롤러코스터가 운행할 때마다 다음 규칙에 따라 손님을 탑승시킨다. 이 과정을 대기열에 손님이 남지 않을 때까지 반복한다.
JAG의 폐장 시간이 임박했기 때문에, 당신은 인접한 팀끼리 대기 순서를 최대 한 번 바꾸어서 롤러코스터의 운행 횟수를 줄일 수 없을지 고민하고 있다. 구체적으로 당신은 다음 동작을 최대 한 번 수행할 수 있다.
위의 동작을 최적으로 수행했을 때, 대기열의 모든 손님을 수용하는 데 필요한 롤러코스터 운행 횟수의 최솟값을 구하는 프로그램을 작성하여라. 대기열에 새로운 팀이 추가되거나 기존 팀이 대기열에서 벗어나는 경우는 생각하지 않는다.
입력
입력은 50개 이하의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 다음과 같이 주어진다.
첫째 줄에는 대기열에 있는 팀의 수 N과 롤러코스터의 정원 M이 주어진다. (2 ≤ N ≤ 2×105, 1 ≤ M ≤ 109)
둘째 줄에는 N개의 정수 a1, a2, ..., aN이 주어진다. 이때 ai는 대기열의 i번째 팀의 인원수이다. (1 ≤ ai ≤ M)
모든 테스트 케이스에 걸쳐 N의 합은 2×106 이하이다.
입력의 끝에는 0이 두 개 주어진다.
출력
각 테스트 케이스마다 문제의 정답을 한 줄로 출력한다.