สมมติว่าเรามีอาร์เรย์ที่เรียกว่า สินค้าคงคลัง โดยที่สินค้าคงคลัง [i] แทนจำนวนลูกบอลสี ith ที่เรามีในตอนแรก นอกจากนี้เรายังมีค่าที่เรียกว่าคำสั่งซื้อซึ่งแสดงถึงจำนวนลูกบอลทั้งหมดที่ลูกค้าต้องการ เราสามารถขายลูกบอลในลำดับใดก็ได้ ในสินค้าคงคลังของเรามีลูกบอลหลากสี ลูกค้าต้องการลูกบอลสีใดก็ได้ ตอนนี้คุณค่าของลูกบอลมีความพิเศษในธรรมชาติ มูลค่าของลูกบอลสีแต่ละลูกคือจำนวนลูกบอลสีนั้นที่เรามีในคลังของเรา ดังนั้นถ้าตอนนี้เรามีลูกบอลสีน้ำเงิน 6 ลูก ลูกค้าจะจ่าย 6 สำหรับลูกบอลสีน้ำเงินลูกแรก จากนั้นเหลือลูกบอลสีน้ำเงินเพียง 5 ลูก ดังนั้นลูกสีน้ำเงินถัดไปจึงมีค่าเท่ากับ 5 เราต้องหามูลค่ารวมสูงสุดที่เราจะได้รับหลังจากขายคำสั่งซื้อลูกบอลสี หากคำตอบมีขนาดใหญ่เกินไป ให้ส่งคืนโมดูล 10^9 + 7
ดังนั้นหากอินพุตเป็นเหมือนสินค้าคงคลัง =[5,7] คำสั่งซื้อ =6 ผลลัพธ์จะเป็น 31 เพราะเราสามารถขายลูกบอลสีแรกสองครั้งในราคา (5,4) และลูกบอลสีที่สอง 4 ครั้ง (7 ,6,5,4) ดังนั้น กำไรรวม 5+4+7+6+5+4 =31
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ต่ำ :=0, สูง :=10000000
-
ในขณะที่ต่ำ <สูง ทำ
-
mid :=ผลหารของ (ต่ำ + สูง)/2
-
s :=0
-
สำหรับแต่ละ i ในสินค้าคงคลัง ทำ
-
ถ้าฉัน> กลาง แล้ว
-
s :=s + i - กลาง
-
-
-
ถ้า s> สั่งแล้ว
-
ต่ำ :=กลาง + 1
-
-
มิฉะนั้น
-
สูง :=กลาง
-
-
-
mid :=ผลหารของ (ต่ำ + สูง)/2
-
ตอบ :=0
-
สำหรับแต่ละ i ในสินค้าคงคลัง ทำ
-
ถ้าฉัน> กลาง แล้ว
-
ans :=ans + ผลหารของ (i*(i+1)/2) - ผลหารของ (mid*(mid+1)/2)
-
คำสั่ง :=คำสั่ง - i-mid
-
-
-
ans :=ans + orders * mid
-
ส่งคืน mod (10^9 + 7)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(inventory, orders): low = 0 high = 10000000 while low < high: mid = (low+high)//2 s = 0 for i in inventory: if i > mid: s += i-mid if s > orders: low = mid+1 else: high = mid mid = (low+high)//2 ans = 0 for i in inventory: if i > mid: ans += i*(i+1)//2 - mid*(mid+1)//2 orders -= i-mid ans += orders*mid return ans % (10**9 + 7) inventory = [5,7] orders = 6 print(solve(inventory, orders))
อินพุต
[6,8,7,11,5,9], [0,0,2], [2,3,5]
ผลลัพธ์
31
