Basic knowledge points involved in this article
C++ algorithm: principles, source code and test cases of prefix sum, prefix product, prefix XOR including course videos
Title
You are given n packages, and you need to put them in boxes, one package in each box. There are a total of m suppliers offering boxes of different sizes (each specification has an infinite number of boxes). If the size of a package is less than or equal to the size of a box, then the package can be placed in the box.
The size of the packages is represented by an integer array packages, where packages[i] is the size of the i-th package. Suppliers are represented by a two-dimensional array of boxes, where boxes[j] is an array of all box sizes provided by the j-th supplier.
You want to choose a supplier and only use boxes from that supplier so that the total wasted space is minimized. For each box containing a package, we define the wasted space equal to the size of the box – the size of the package. Total wasted space is the sum of wasted space in all boxes.
For example, if you want to put a package of size [2,3,5] in a box with size array [4,8], you can put two packages of size 2 and 3 into two boxes of size 4 boxes, while packing size 5 packages into size 8 boxes. The total wasted space is (4-2) + (4-3) + (8-5) = 6 .
Please choose the best box supplier to minimize the total wasted space. If you cannot fit all packages into the box, return -1 . Since the answer may be very large, return its result modulo 109 + 7.
Example 1:
Input: packages = [2,3,5], boxes = [[4,8],[2,8]]
Output: 6
Explanation: Choose the first supplier optimally, with two boxes of size 4 and one box of size 8.
The total wasted space is (4-2) + (4-3) + (8-5) = 6 .
Example 2:
Input: packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
Output: -1
Explanation: No box can hold a package of size 5.
Example 3:
Input: packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
Output: 9
Explanation: Choose the third supplier optimally, with two boxes of size 5, two boxes of size 10 and two boxes of size 14.
The total wasted space is (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9 .
Parameter range:
n == packages.length
m==boxes.length
1 <= n <= 105
1 <= m <= 105
1 <= packages[i] <= 105
1 <= boxes[j].length <= 105
1 <= boxes[j][k] <= 105
sum(boxes[j].length) <= 105
The elements in boxes[j] are different from each other.
Analysis
Ideas
Use v to represent the boxes owned by a certain merchant, sorted in ascending order. A box of size v[0] contains all boxes whose size is less than or equal to v[0], that is, the number of boxes with v[0] is equal to the number of boxes with size [0, v[0]]. In the same way, the number of v[1] is equal to the number of packages with size (v[0], v[1]].
Note
If the merchant’s largest box size is smaller than the largest package size, this merchant cannot be selected. If all merchants cannot be selected, -1 is returned. If there are multiple boxes larger than the largest package size, only the first of those boxes will be used.
Calculate the number of packages using prefix sum, beware of index overflow.
Variable meaning
| iMax | Maximum number Package size |
| vSum | vSum[i] is equal to the number of packages with space less than or equal to i |
| llNeed | The total space of all packages |
| cur | The total space of the boxes provided by the current merchant |
Code
Core code
class Solution {
public:
int minWastedSpace(vector & amp; packages, vector
int iMax = *std::max_element(packages.begin(), packages.end());
vector vNum(iMax + 1);
long long llNeed = 0;
for (const auto & n : packages)
{
vNum[n] + + ;
llNeed + = n;
}
vector vSum = { 0 };//vSum[i] is equal to the number of packages with space less than or equal to i
for (int i = 1; i <= iMax; i + + )
{
vSum.emplace_back(vSum.back() + vNum[i]);
}
long long llHas = LLONG_MAX;
for (auto & amp; v : boxes)
{
sort(v.begin(), v.end());
if (v.back() < iMax)
{
continue;
}
int pre = 0;
long long cur = 0;//Total capacity of packages provided on the current space
for (auto & n : v)
{
cur + = ((long long)vSum[min(n,iMax)] – vSum[pre]) * n;
pre = n;
if (n >= iMax)
{
break;
}
}
llHas = min(llHas, cur);
}
if (LLONG_MAX == llHas)
{
return -1;
}
const long long llMod = 1e9 + 7;
return (llHas – llNeed) % llMod;
}
};
Test cases
template
void Assert(const vector & amp; v1, const vector & amp; v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i + + )
{
assert(v1[i] == v2[i]);
}
}
template
void Assert(const T & t1, const T & t2)
{
assert(t1 == t2);
}
int main()
{
Solution slug;
vector packages;
vector
int res = 0;
packages = { 3,5,8,10,11,12 };
boxes = { {12},{11,9},{10,5,14} };
res = slu.minWastedSpace(packages, boxes);
Assert(9, res);
packages = { 3, 5, 8, 7, 5, 8, 10, 11, 12 };
boxes = { {12},{11,9},{10,5,14} };
res = slu.minWastedSpace(packages, boxes);
Assert(14, res);
packages = { 2,3,5 };
boxes = { {4,8},{2,8} };
res = slu.minWastedSpace(packages, boxes);
Assert(6, res);
packages = { 2,3,5,8,7,6 };
boxes = { {4,8},{2,8} };
res = slu.minWastedSpace(packages, boxes);
Assert(9, res);
//CConsole::Out(res);
}
Old code in March 2023
class Solution {
public:
int minWastedSpace(vector & amp; packages, vector
std::sort(packages.begin(), packages.end());
vector vSums(1);
for (const auto & amp; pack : packages)
{
vSums.emplace_back(pack + vSums.back());
}
std::priority_queueque;
for (auto & amp; v : boxes)
{
std::sort(v.begin(), v.end());
long long llCur = 0;
int iHasDo = 0;
for (int j = 0; j < v.size(); j + + )
{
auto iCurDoEnd = std::upper_bound(packages.begin() + iHasDo, packages.end(), v[j]) – packages.begin();
long long llCurBox = (long long)v[j] * (iCurDoEnd – iHasDo) – (vSums[iCurDoEnd] – vSums[iHasDo]);
llCur + = llCurBox;
iHasDo = iCurDoEnd;
}
if (packages.size() == iHasDo)
{
que.push(llCur);
if (que.size() > 1)
{
que.pop();
}
}
}
return que.size() ? C1097Int<>(que.top()).ToInt() : -1 ;
}
};
Extended reading
Video course
Effective learning: clear goals, timely feedback, stretching zone (appropriate difficulty), you can learn simple courses first, please go to CSDN Academy and listen to the explanation of Baiyin Lecturer (that is, I).
https://edu.csdn.net/course/detail/38771
how fast do you want
A battle has quickly formed. To share the worries of your boss, please learn C# onboarding training, C++ onboarding training and other courses.
https://edu.csdn.net/lecturer/6176
Related downloads
If you want to know the superior learning algorithm, please download the doc version of “Algorithm Book When You Hear the Defects”
https://download.csdn.net/download/he_zhidan/88348653
| What I want to say to you all
|
|-|
|Rejoicing when you hear defects is a good wish, to find problems early, correct them early, and save money for the boss. |
| The origin of the Mohist name: Everything is recorded in Mohism. |
|If the program is a dragon, then the algorithm is his key point|
Test environment
Operating system: win7 Development environment: VS2019 C++ 17
Or operating system: win10 development environment:
VS2022 C++ 17
