【C++二分查找 贪心】1648. 销售价值减少的颜色球|2050

本文涉及知识点

C++贪心
C++二分查找

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

你有一些球的库存 inventory ，里面包含着不同颜色的球。一个顾客想要 任意颜色 总数为 orders 的球。
这位顾客有一种特殊的方式衡量球的价值：每个球的价值是目前剩下的 同色球 的数目。比方说还剩下 6 个黄球，那么顾客买第一个黄球的时候该黄球的价值为 6 。这笔交易以后，只剩下 5 个黄球了，所以下一个黄球的价值为 5 （也就是球的价值随着顾客购买同色球是递减的）
给你整数数组 inventory ，其中 inventory[i] 表示第 i 种颜色球一开始的数目。同时给你整数 orders ，表示顾客总共想买的球数目。你可以按照 任意顺序 卖球。
请你返回卖了 orders 个球以后 最大 总价值之和。由于答案可能会很大，请你返回答案对 109 + 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 <= 105
1 <= inventory[i] <= 109
1 <= orders <= min(sum(inventory[i]), 109)

二分查找+贪心

令最后一个球的价值为x，则不存在球大于x，否则与此球交换。
Cnt(x)：价值大于x的球数量。
Check 函数： Cnt(x) >= order
二分类型：查找尾端
Check函数的参数：[1,1e9]
返回值：cnt1 = order - Cnt(ret+1) 价值大于ret的价值和+cnt1*ret。

代码

核心代码

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++**实现。