Giả sử chúng ta đã đưa ra một danh sách các con số được gọi là xếp hạng và điều này đang hiển thị điểm hiệu suất của các lập trình viên. Bây giờ người quản lý muốn đưa ra 1000 Rs cho mỗi người lập trình ngoại trừ nếu hai người lập trình liền kề nhau, họ muốn trả cho người lập trình hoạt động tốt hơn ít nhất là 1000 Rs so với người hoạt động kém hơn. Chúng tôi phải tìm số tiền tối thiểu mà người quản lý có thể trả theo các ràng buộc trên.
Vì vậy, nếu đầu vào giống như xếp hạng =[1, 2, 5, 1], thì đầu ra sẽ là 7000, vì số tiền tối thiểu chúng tôi có thể trả cho mỗi người lập trình tương ứng là [1000, 2000, 3000, 1000]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
pay:=một danh sách có kích thước giống như xếp hạng, ban đầu tất cả các giá trị là 1
-
đối với tôi trong phạm vi từ 1 đến cỡ xếp hạng - 1, làm
-
nếu xếp hạng [i]> xếp hạng [i-1], thì
-
pay [i]:=pay [i-1] +1
-
-
-
đối với tôi trong phạm vi kích thước xếp hạng -2 đến 0, giảm 1, thực hiện
-
nếu xếp hạng [i]> xếp hạng [i + 1] thì
-
pay [i]:=tối đa pay [i] và trả [i + 1] +1
-
-
-
lợi nhuận (tổng của các yếu tố thanh toán) * 1000
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))
Đầu vào
[1, 2, 5, 1]
Đầu ra
7000