C++前缀和算法的应用：装包裹的最小浪费空间 原理源码测试用例

class Solution {
public:
int minWastedSpace(vector& packages, vector<vector>& boxes) {
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] 等于 空间小于等于i 的包裹数量
for (int i = 1; i <= iMax; i++)
{
vSum.emplace_back(vSum.back() + vNum[i]);
}
long long llHas = LLONG_MAX;
for (auto& v : boxes)
{
sort(v.begin(), v.end());
if (v.back() < iMax)
{
continue;
}
int pre = 0;
long long cur = 0;//当前空间上提供的包裹的总容量
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;
}
};

template
void Assert(const vector& v1, const vector& 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 slu;
vector packages;
vector<vector>boxes;
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);

class Solution {
public:
int minWastedSpace(vector& packages, vector<vector>& boxes) {
std::sort(packages.begin(), packages.end());
vector vSums(1);
for (const auto& pack : packages)
{
vSums.emplace_back(pack + vSums.back());
}
std::priority_queue que;
for (auto& 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 ;
}
};