Chương trình tìm kiếm lợi nhuận tối đa bằng cách bán các quả bóng màu có giá trị giảm dần bằng Python

Giả sử chúng ta có một mảng được gọi là khoảng không quảng cáo, trong đó khoảng không quảng cáo [i] đại diện cho số quả bóng có màu thứ i mà chúng ta có ban đầu. Chúng tôi cũng có một giá trị được gọi là đơn đặt hàng, đại diện cho tổng số quả bóng mà khách hàng muốn. chúng tôi có thể bán các quả bóng theo bất kỳ đơn đặt hàng nào. Trong kho của chúng tôi có các quả bóng màu khác nhau, khách hàng muốn quả bóng có màu nào. Bây giờ giá trị của các quả bóng là đặc biệt trong tự nhiên. Giá trị của mỗi quả bóng màu là số quả bóng cùng màu mà chúng ta có trong kho của mình. Vì vậy, nếu chúng tôi hiện có 6 quả bóng màu xanh lam, khách hàng sẽ trả 6 quả bóng màu xanh đầu tiên. Khi đó chỉ còn lại 5 quả bóng màu xanh, vì vậy quả bóng màu xanh tiếp theo có giá trị là 5. Chúng ta phải tìm tổng giá trị lớn nhất mà chúng ta có thể nhận được sau khi bán đơn đặt hàng các quả bóng màu. Nếu câu trả lời quá lớn, hãy trả lại nó theo mô-đun 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là hàng tồn kho =[5,7], đơn đặt hàng =6, thì đầu ra sẽ là 31 vì chúng ta có thể bán quả bóng màu thứ nhất hai lần với giá (5,4) và quả bóng màu thứ hai 4 lần (7 , 6,5,4), vậy tổng lợi nhuận 5 + 4 + 7 + 6 + 5 + 4 =31

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• thấp:=0, cao:=10000000

• trong khi thấp

  • mid:=quotient of (low + high) / 2

  • s:=0

  • đối với mỗi tôi trong kho, hãy thực hiện

    • nếu tôi> giữa, thì

      • s:=s + i - giữa

  • if s> đơn đặt hàng, sau đó

    • thấp:=mid + 1

  • nếu không,

    • cao:=giữa

• mid:=quotient of (low + high) / 2

• ans:=0

• đối với mỗi tôi trong kho, hãy thực hiện

  • nếu tôi> giữa, thì

    • ans:=ans + thương số của (i * (i + 1) / 2) - thương số của (giữa * (giữa + 1) / 2)

    • đơn hàng:=đơn đặt hàng - i-mid

• ans:=ans + đơn đặt hàng * giữa

• return ans mod (10 ^ 9 + 7)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[6,8,7,11,5,9], [0,0,2], [2,3,5]

Đầu ra

31