숫자 n이 n명을 나타내고 두 개의 동일한 투표 기계가 있다고 가정합니다. 또한 time[i]가 i번째 사람이 어떤 기계에서든 투표하는 데 소비한 총 시간을 나타내도록 크기가 n인 시간이라는 배열이 있습니다. 한 번에 두 기계 각각에 한 사람만 있을 수 있습니다. 또한 기계가 작동하는 최대 허용 시간을 나타내는 또 다른 값 x가 있으므로 모든 사람이 투표할 수 있는지 여부를 확인해야 합니다.
따라서 입력이 n =3, x =7, 시간 =[3, 5, 3]과 같으면 출력은 True가 됩니다. 시간 t0에 0번째 사람이 첫 번째 기계로 가고 1번째 사람이 두 번째 기계로 가기 때문입니다. 이제 시간 t3에 첫 번째 기계가 무료입니다. 이제 2인칭 첫 번째 기계로 이동하고 t5 시간에 두 번째 기계가 무료이고 t6 시간에 첫 번째 기계가 무료이므로 모든 참가자가 제 시간에 투표했습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- total_sum :=시간의 모든 요소의 합
- total_sum <=x이면
- 참 반환
- 목록 시간 정렬
- prev_sum :=시간과 크기가 같고 0으로 채워지는 배열
- prev_sum[0] :=시간[0]
- 범위 1에서 prev_sum 크기까지의 i에 대해
- prev_sum[i] :=prev_sum[i - 1] + 시간[i]
- 0에서 prev_sum 크기까지의 i에 대해
- i + 1 범위에서 prev_sum - 1 크기의 j에 대해
- temp_sum :=prev_sum[i] + (total_sum - prev_sum[j])
- temp_sum <=x이고 total_sum - temp_sum <=x이면
- 참 반환
- i + 1 범위에서 prev_sum - 1 크기의 j에 대해
- 거짓을 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
def solve(n, x, time): total_sum = sum(time) if total_sum <= x: return True time.sort() prev_sum = [0 for i in range(len(time))] prev_sum[0] = time[0] for i in range(1, len(prev_sum)): prev_sum[i] = prev_sum[i - 1] + time[i] for i in range(0, len(prev_sum)): for j in range(i + 1, len(prev_sum)): temp_sum = (prev_sum[i] + (total_sum - prev_sum[j])) if temp_sum <= x and total_sum - temp_sum <= x: return True return False n = 3 x = 7 time = [3, 5, 3] print(solve(n, x, time))
입력
3, 7, [3, 5, 3]
출력
True