สมมติว่าเรามีรายการตัวเลขสองรายการที่เรียกว่า nums และ cost ทีนี้ลองพิจารณา มีการดำเนินการที่เราสามารถเพิ่มหรือลด nums[i] สำหรับ cost cost[i] ได้ เราสามารถดำเนินการเหล่านี้จำนวนเท่าใดก็ได้ และเราต้องการทำให้องค์ประกอบทั้งหมดมีค่าเท่ากันในจำนวน เราต้องหาต้นทุนรวมขั้นต่ำที่ต้องการ
ดังนั้นหากอินพุตเท่ากับ nums =[3, 2, 4] ต้นทุน =[1, 10, 2] ผลลัพธ์จะเป็น 5 ราวกับว่าเราสามารถลดจำนวน 3 เป็น 2 ในราคา 1 แล้ว เราลดได้ 4 ครั้ง ครั้งละ 2 ครั้ง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชั่น helper() นี้จะเป็นเป้าหมาย
-
รวม :=0
-
สำหรับแต่ละ i,n ในการแจกแจง (nums) ทำ
-
ถ้าเป้าหมายไม่เหมือนกับ n แล้ว
-
Total :=total + |n-target| * ค่าใช้จ่าย[i]
-
-
-
ผลตอบแทนรวม
-
จากวิธีหลัก ให้ทำดังนี้:
-
ต่ำ :=0, สูง :=สูงสุดของ nums
-
ในขณะที่ต่ำ <สูงไม่เป็นศูนย์ ทำ
-
กลาง :=(ต่ำ + สูง) / 2
-
ถ้า helper(mid)
-
สูง :=กลาง
-
-
มิฉะนั้น
-
ต่ำ :=กลาง + 1
-
-
-
ผู้ช่วยกลับ(ต่ำ)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution: def solve(self, nums, costs): def helper(target): total = 0 for i,n in enumerate(nums): if target != n: total += abs(n-target) * costs[i] return total low,high = 0, max(nums) while low < high: mid = low + high >> 1 if helper(mid) < helper (mid+1): high = mid else: low = mid + 1 return helper(low) ob = Solution() nums = [3, 2, 4] costs = [1, 10, 2] print(ob.solve(nums, costs))
อินพุต
[3, 2, 4], [1, 10, 2]
ผลลัพธ์
5
