0에서 n-1까지 번호가 지정된 n개의 도시가 있고 n개의 방향 도로가 있다고 가정합니다. 우리는 도시 i에서 도시 (i + 1) % n [0 to 1 to 2 to .... to N - 1 to 0]으로 여행할 수 있습니다. 우리는 차를 가지고 있습니다. 우리 차의 연료 탱크 용량은 캡 단위입니다. 도시 i의 시작 부분에 사용할 수 있는 연료[i] 단위의 연료가 있으며 자동차는 도시 i에서 (i + 1) %n까지 이동하는 데 비용[i] 단위의 연료가 필요합니다. 모든 도시를 여행하고 출발한 동일한 도시에 도달하려면 자동차를 출발할 수 있는 곳에서 몇 개의 도시를 찾아야 할까요?
따라서 입력이 cap =3 연료 =[3,1,2] 비용 =[2,2,2]와 같으면 두 가지 가능한 솔루션이 있기 때문에 출력은 2가 됩니다.
-
우리는 도시 0에서 시작하여 탱크에 3단위의 연료를 채우고 2단위의 연료를 사용하여 도시 1로 이동할 수 있습니다. 탱크에는 한 단위가 남아 있습니다. 도시 1에서 1단위의 연료를 취한 후 자동차는 2단위의 연료를 가지고 있으며 우리는 2단위의 연료를 사용하여 도시 2로 이동할 수 있습니다. 이제 연료 탱크가 비어 있습니다. 도시 2에서 2갤런의 연료를 보급한 후 2갤런의 연료를 사용하여 도시 0으로 돌아갑니다.
-
우리는 도시 2에서 시작하여 2단위의 연료를 차에 채우고 도시 0으로 여행할 수 있습니다. 그런 다음 도시 0에서 3갤런의 연료를 보급한 후 도시 1로 이동하고 1단위의 연료를 갖게 됩니다. 그런 다음 도시 1에서 1단위의 연료를 보급할 수 있으며 이제 2단위의 연료를 가지고 도시 2로 이동할 수 있습니다.
그러나 우리는 도시 1에서 시작할 수 없으며 연료가 1단위만 존재하지만 도시 2로 여행하려면 2갤런이 필요합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=연료의 크기
- req :=크기가 n이고 0으로 채워지는 배열
- 0 ~ 1 범위의 k에 대해
- n-1에서 0 사이의 i에 대해 1만큼 감소, do
- nexti :=(i + 1) 모드 n
- req[i] :=최대값 0 및 req[nexti] + 비용[i] - 연료[i]
- 최소값이 (req[i] + fuel[i] 및 cap) - 비용[i]
- 0을 반환
- n-1에서 0 사이의 i에 대해 1만큼 감소, do
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(cap, fuel, costs):
n = len(fuel)
req = [0] * n
for k in range(2):
for i in range(n-1, -1, -1):
nexti = (i + 1) % n
req[i] = max(0, req[nexti] + costs[i] - fuel[i])
if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
return 0
return sum(1 for r in req if r == 0)
cap = 3
fuel = [3,1,2]
costs = [2,2,2]
print(solve(cap, fuel, costs)) 입력
3, [3,1,2], [2,2,2]
출력
2