本文涉及的基础知识点

C++二分查找

贪心

LeetCode1648. 销售价值减少的颜色球

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

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

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

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

示例 1：

输入：inventory = [2,5], orders = 4

输出：14

解释：卖 1 个第一种颜色的球（价值为 2 )，卖 3 个第二种颜色的球（价值为 5 + 4 + 3）。

最大总和为 2 + 5 + 4 + 3 = 14 。

示例 2：

输入：inventory = [3,5], orders = 6

输出：19

解释：卖 2 个第一种颜色的球（价值为 3 + 2），卖 4 个第二种颜色的球（价值为 5 + 4 + 3 + 2）。

最大总和为 3 + 2 + 5 + 4 + 3 + 2 = 19 。

示例 3：

输入：inventory = [2,8,4,10,6], orders = 20

输出：110

示例 4：

输入：inventory = [1000000000], orders = 1000000000

输出：21

解释：卖 1000000000 次第一种颜色的球，总价值为 500000000500000000 。 500000000500000000 对 109 + 7 取余为 21 。

提示：

1 <= inventory.length <= 10⁵

1 <= inventory[i] <= 10⁹

1 <= orders <= min(sum(inventory[i]), 10⁹)

二分查找+贪心

令最后一个球的价值为x，则不存在球大于x，否则与此球交换。

Cnt(x)：价值大于x的球数量。

Check 函数： Cnt(x) >= order

二分类型：查找尾端

Check函数的参数：[1,1e9]

返回值：cnt1 = order - Cnt(ret+1) 价值大于ret的价值和+cnt1*ret。

代码

核心代码

<code>template<class INDEX_TYPE>

class CBinarySearch

{ -- -->

public:

CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) { }

template<class _Pr>

INDEX_TYPE FindFrist( _Pr pr)

{

auto left = m_iMin - 1;

auto rightInclue = m_iMax;

while (rightInclue - left > 1)

{

const auto mid = left + (rightInclue - left) / 2;

if (pr(mid))

{

rightInclue = mid;

}

else

{

left = mid;

}

}

return rightInclue;

}

template<class _Pr>

INDEX_TYPE FindEnd( _Pr pr)

{

int leftInclude = m_iMin;

int right = m_iMax + 1;

while (right - leftInclude > 1)

{

const auto mid = leftInclude + (right - leftInclude) / 2;

if (pr(mid))

{

leftInclude = mid;

}

else

{

right = mid;

}

}

return leftInclude;

}

protected:

const INDEX_TYPE m_iMin, m_iMax;

};

class Solution {

public:

int maxProfit(vector<int>& inventory, int orders) {

auto Check = [&](int mid) {

long long cnt = 0;

for (const auto& n : inventory) {

cnt += max(0, n - mid+1);

}

return cnt >= orders;

};

auto ret = CBinarySearch<int>(1, 1e9).FindEnd(Check);

long long llPro = 0;

for (const long long n : inventory) {

if (n > ret) {

orders -= (n - ret);

llPro += (n + ret + 1) * (n - ret) / 2;

}

}

llPro += ret * (long long)orders;

return llPro %((int)1e9 + 7);

}

};

单元测试

vector<int> inventory;

int orders;

TEST_METHOD(TestMethod11)

{

inventory = { 2,5 }, orders = 4;

auto res = Solution().maxProfit(inventory, orders);

AssertEx(14, res);

}

TEST_METHOD(TestMethod12)

{

inventory = { 3,5 }, orders = 6;

auto res = Solution().maxProfit(inventory, orders);

AssertEx(19, res);

}

TEST_METHOD(TestMethod13)

{

inventory = { 2,8,4,10,6 }, orders = 20;

auto res = Solution().maxProfit(inventory, orders);

AssertEx(110, res);

}

TEST_METHOD(TestMethod14)

{

inventory = { 1000000000 }, orders = 1000000000;

auto res = Solution().maxProfit(inventory, orders);

AssertEx(21, res);

}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。