sell-diminishing-valued-colored-balls

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You have an <code>inventory</code> of different colored balls, and there is a customer that wants <code>orders</code> balls of any color.

The customer weirdly values the colored balls. Each colored ball&#39;s value is the number of balls of that color&nbsp;you currently have in your <code>inventory</code>. For example, if you own <code>6</code> yellow balls, the customer would pay <code>6</code> for the first yellow ball. After the transaction, there are only <code>5</code> yellow balls left, so the next yellow ball is then valued at <code>5</code> (i.e., the value of the balls decreases as you sell more to the customer).

You are given an integer array, <code>inventory</code>, where <code>inventory[i]</code> represents the number of balls of the <code>ith</code> color that you initially own. You are also given an integer <code>orders</code>, which represents the total number of balls that the customer wants. You can sell the balls in any order.

Return the maximum total value that you can attain after selling <code>orders</code> colored balls. As the answer may be too large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/05/jj.gif" style="width: 480px; height: 270px;" />
<pre>
Input: inventory = [2,5], orders = 4
Output: 14
Explanation: Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
The maximum total value is 2 + 5 + 4 + 3 = 14.
</pre>

Example 2:

<pre>
Input: inventory = [3,5], orders = 6
Output: 19
Explanation: Sell the 1st color 2 times (3 + 2) and the 2nd color 4 times (5 + 4 + 3 + 2).
The maximum total value is 3 + 2 + 5 + 4 + 3 + 2 = 19.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= inventory.length &lt;= 105</code></li>
	<li><code>1 &lt;= inventory[i] &lt;= 109</code></li>
	<li><code>1 &lt;= orders &lt;= min(sum(inventory[i]), 109)</code></li>
</ul>

maxProfit

Sell Diminishing-Valued Colored Balls

Maximum Running Time of N Computers

maximum-running-time-of-n-computers

同时运行 N 台电脑的最长时间

Greedy

Array

Math

Binary Search

Sorting

Heap (Priority Queue)

你有一些球的库存 <code>inventory</code> ，里面包含着不同颜色的球。一个顾客想要 任意颜色 总数为 <code>orders</code> 的球。

这位顾客有一种特殊的方式衡量球的价值：每个球的价值是目前剩下的 同色球 的数目。比方说还剩下 <code>6</code> 个黄球，那么顾客买第一个黄球的时候该黄球的价值为 <code>6</code> 。这笔交易以后，只剩下 <code>5</code> 个黄球了，所以下一个黄球的价值为 <code>5</code> （也就是球的价值随着顾客购买同色球是递减的）

给你整数数组 <code>inventory</code> ，其中 <code>inventory[i]</code> 表示第 <code>i</code> 种颜色球一开始的数目。同时给你整数 <code>orders</code> ，表示顾客总共想买的球数目。你可以按照 任意顺序 卖球。

请你返回卖了 <code>orders</code> 个球以后 最大 总价值之和。由于答案可能会很大，请你返回答案对 <code>109 + 7</code> 取余数 的结果。

 

示例 1：
<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/08/jj.gif" style="width: 480px; height: 270px;" />
<pre>
输入：inventory = [2,5], orders = 4
输出：14
解释：卖 1 个第一种颜色的球（价值为 2 )，卖 3 个第二种颜色的球（价值为 5 + 4 + 3）。
最大总和为 2 + 5 + 4 + 3 = 14 。
</pre>

示例 2：

<pre>
输入：inventory = [3,5], orders = 6
输出：19
解释：卖 2 个第一种颜色的球（价值为 3 + 2），卖 4 个第二种颜色的球（价值为 5 + 4 + 3 + 2）。
最大总和为 3 + 2 + 5 + 4 + 3 + 2 = 19 。
</pre>

示例 3：

<pre>
输入：inventory = [2,8,4,10,6], orders = 20
输出：110
</pre>

示例 4：

<pre>
输入：inventory = [1000000000], orders = 1000000000
输出：21
解释：卖 1000000000 次第一种颜色的球，总价值为 500000000500000000 。 500000000500000000 对 109 + 7 取余为 21 。
</pre>

 

提示：

<ul>
	<li><code>1 <= inventory.length <= 105</code></li>
	<li><code>1 <= inventory[i] <= 109</code></li>
	<li><code>1 <= orders <= min(sum(inventory[i]), 109)</code></li>
</ul>