4개의 캐빈이 있는 관람차가 있고 각 캐빈에 4명의 승객이 탑승할 수 있다고 가정합니다. 바퀴는 반시계 방향으로 회전하며, 1회전할 때마다 '달리기' 비용이 듭니다. 이제 n개의 항목을 포함하는 배열 'cust'가 있으며 각 항목 i는 i번째 회전 전에 관람차에 탑승하기 위해 기다리는 사람들의 수를 나타냅니다. 휠에 탑승하기 위해서는 각 고객이 일정 금액의 '보드'를 지불해야 하며, 그 만큼의 금액은 휠을 시계 반대 방향으로 한 바퀴 회전하는 것입니다. 선실에 빈 좌석이 있으면 줄을 서서 기다리는 사람들을 기다리지 마십시오. 따라서 데이터가 주어지면 이익을 최대화하기 위해 필요한 최소 회전량을 찾아야 합니다.
따라서 입력이 cust =[6,4], board =6, run =4와 같으면 출력은 3
이 됩니다.처음에는 6명이 줄을 서서 기다리고 있습니다. 따라서 처음에는 4명이 첫 번째 캐빈에 탑승하고 나머지는 다음 캐빈을 기다립니다.
바퀴가 회전하고 두 번째 캐빈이 도착합니다. 그 사이 4명이 더 줄을 섭니다. 따라서 대기 중인 다음 4명이 다음 캐빈에 탑승합니다.
바퀴가 다시 회전하고 나머지 3명의 고객은 다음 객실에 탑승합니다.
따라서 모든 고객에게 서비스를 제공하려면 최소한 3번의 순환이 필요합니다.
이러한 회전으로 얻을 수 있는 최대 이익은 (10 * 6) - (3 * 4) =48입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
해상도 :=-1
-
mst :=0
-
tmp :=0
-
중량 :=0
-
cust의 각 인덱스 idx 및 값 val에 대해 수행
-
중량 :=중량 + 발
-
chg :=최소 (4, wt)
-
중량 :=중량 - 채널
-
tmp :=tmp + chg * 보드 - 실행
-
mst
-
해상도 :=idx + 1
-
mst :=tmp
-
-
-
x :=중량 / 4
-
y :=중량 모드 4
-
4 * 보드> 실행이면
-
res :=res + x
-
-
y * 보드> 실행이면
-
해상도 :=해상도 + 1
-
-
반환 해상도
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(cust, board, run):
res = -1
mst = 0
tmp = 0
wt = 0
for idx, val in enumerate(cust):
wt += val
chg = min(4, wt)
wt -= chg
tmp += chg * board - run
if mst < tmp:
res, mst = idx+1, tmp
x, y = divmod(wt, 4)
if 4 * board > run:
res += x
if y * board > run:
res += 1
return res
print(solve([6,4], 6, 4)) 입력
[6,4], 6, 4
출력
3