평가라고 하는 숫자 목록을 제공하고 이것이 코더의 성능 점수를 표시한다고 가정합니다. 이제 관리자는 두 코더가 인접해 있는 경우를 제외하고 모든 코더에게 1000루피를 주기를 원합니다. 단, 더 나은 코더에게 더 낮은 1000루피를 더 지불하고 싶습니다. 위의 제약 조건에 따라 관리자가 지불할 수 있는 최소 금액을 찾아야 합니다.
따라서 입력이 Ratings =[1, 2, 5, 1]과 같으면 출력은 7000이 됩니다. 각 코더에 대해 지불할 수 있는 최소값은 [1000, 2000, 3000, 1000]
입니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
pay:=등급과 동일한 크기 목록, 처음에는 모든 값이 1입니다.
-
범위 1에서 등급 크기 - 1에 있는 i에 대해 수행
-
등급[i]> 등급[i-1]이면
-
지불[i] :=지불[i-1]+1
-
-
-
등급 범위 크기의 i에 대해 -2에서 0, 1 감소, 수행
-
등급[i]> 등급[i+1]이면
-
pay[i] :=pay[i]와 pay[i+1]+1의 최대값
-
-
-
return (pay 요소의 합) *1000
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, ratings): pay=[1 for _ in ratings] for i in range(1, len(ratings)): if ratings[i] > ratings[i-1]: pay[i] = pay[i-1]+1 for i in range(len(ratings)-2,-1,-1): if ratings[i] > ratings[i+1]: pay[i] = max(pay[i], pay[i+1]+1) return sum(pay)*1000 ob = Solution() ratings = [1, 2, 5, 1] print(ob.solve(ratings))
입력
[1, 2, 5, 1]
출력
7000