Chương trình tìm số tiền tối thiểu trả cho nhân viên xuất sắc trong Python

Cho danh sách điểm hiệu suất. Mỗi người ít nhất 1000. Nếu hai người liền kề, người tốt hơn phải nhận nhiều hơn ít nhất 1000. Tìm tổng tiền tối thiểu.

Ví dụ: → tiền [1000, 2000, 3000, 1000] → tổng 7000.

Giải thuật (Hai pass - Candy problem)

1. Khởi tạo .
2. Pass trái→phải: nếu ratings[i-1] thì .
3. Pass phải→trái: nếu ratings[i+1] thì .
4. Trả về .

Ví dụ minh họa

class Solution:
    def solve(self, ratings):
        pay = [1] * len(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))  # Output: 7000

Đầu vào

[1, 2, 5, 1]

Đầu ra

7000