สมมติว่าเราได้ให้รายการตัวเลขที่เรียกว่าการให้คะแนน และนี่คือการแสดงคะแนนประสิทธิภาพของผู้เขียนโค้ด ตอนนี้ผู้จัดการต้องการให้ Rs 1,000 แก่ coder ทุกคน ยกเว้นว่าถ้า coder สองตัวอยู่ติดกัน พวกเขาต้องการจ่าย coder ที่ทำงานได้ดีกว่า Rs 1000 ให้สูงกว่า Rs 1000 มากกว่าตัวที่แย่กว่า เราต้องหาจำนวนเงินขั้นต่ำที่ผู้จัดการสามารถจ่ายได้ตามข้อจำกัดข้างต้น
ดังนั้น หากอินพุตเหมือนกับการให้คะแนน =[1, 2, 5, 1] ผลลัพธ์จะเป็น 7000 เนื่องจากขั้นต่ำที่เราสามารถจ่ายสำหรับตัวเข้ารหัสแต่ละตัวคือ [1000, 2000, 3000, 1000]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
จ่าย:=รายการขนาดเดียวกับการให้คะแนน เริ่มต้นทุกค่าเป็น 1
-
สำหรับฉันอยู่ในช่วง 1 ถึงขนาดของการให้คะแนน - 1 ทำ
-
ถ้าการให้คะแนน[i]> การให้คะแนน[i-1] แล้ว
-
จ่าย[i] :=จ่าย[i-1]+1
-
-
-
สำหรับฉันในช่วงขนาดการให้คะแนน -2 ถึง 0, ลดลง 1 ทำ
-
ถ้าการให้คะแนน[i]> การให้คะแนน[i+1] แล้ว
-
จ่าย[i] :=จ่ายสูงสุด[i] และจ่าย[i+1]+1
-
-
-
ผลตอบแทน (ผลรวมของการจ่าย) *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
