인벤토리라는 배열이 있다고 가정합니다. 여기서 인벤토리[i]는 처음에 가지고 있는 i번째 색상의 볼 수를 나타냅니다. 또한 고객이 원하는 총 볼 수를 나타내는 order라는 값도 있습니다. 우리는 어떤 순서로 공을 판매할 수 있습니다. 재고에는 다양한 색상의 공이 있으며 고객은 모든 색상의 공을 원합니다. 이제 공의 가치는 본질적으로 특별합니다. 각 색 공의 값은 인벤토리에 있는 해당 색 공의 수입니다. 따라서 현재 6개의 파란색 공이 있는 경우 고객은 첫 번째 파란색 공에 대해 6개를 지불합니다. 그러면 남은 파란색 공은 5개뿐이므로 다음 파란색 공의 가치는 5입니다. 우리는 주문한 색 공을 판매한 후 얻을 수 있는 최대 총 가치를 찾아야 합니다. 답이 너무 크면 모듈로 10^9 + 7을 반환합니다.
따라서 입력이 재고 =[5,7], 주문 =6과 같으면 첫 번째 유색 공을 가격(5,4)으로 두 번 판매하고 두 번째 유색 공을 4번(7) 판매할 수 있기 때문에 출력은 31이 됩니다. ,6,5,4) 따라서 총 이익 5+4+7+6+5+4 =31
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
낮음 :=0, 높음 :=10000000
-
낮은 동안 <높은, 수행
-
mid :=(낮음 + 높음)/2의 몫
-
s :=0
-
인벤토리의 각 i에 대해 수행
-
i> mid이면
-
s :=s + i - 중간
-
-
-
s> 주문이면
-
낮음 :=중간 + 1
-
-
그렇지 않으면
-
높음 :=중간
-
-
-
mid :=(낮음 + 높음)/2의 몫
-
답변 :=0
-
인벤토리의 각 i에 대해 수행
-
i> mid이면
-
ans :=ans + (i*(i+1)/2)의 몫 - (mid*(mid+1)/2)의 몫
-
주문 :=주문 - i-mid
-
-
-
ans :=ans + 주문 * mid
-
모드로 반환 (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