3016. Minimum Number of Pushes to Type Word II
思路：把频率最高的放在 8 个按钮最前面，越低的越后面
实作：
(1) 用 map 把各个字母的频率收集起来
(2) 由高到低排序
(3) 每 8 个字母一起加总，要考虑 residual
运气好很久以前写过 residual iteration
https://github.com/nh60211as/WorldChunkToolCPP/blob/master/WorldChunkToolCPP/
ChunkDecrypter.cpp
class Solution {
public:
int minimumPushes(string word) {
map<char, int> frequency;
for (char c : word) {
frequency[c]++;
}
vector<int> descendingFrequency;
descendingFrequency.reserve(frequency.size());
for (auto const& [key, val] : frequency) {
descendingFrequency.push_back(val);
}
sort(descendingFrequency.rbegin(), descendingFrequency.rend());
constexpr int BUTTON_COUNT = 8;
int result = 0;
int pushRequired = 1;
size_t i = 0;
for (; i < (descendingFrequency.size() / BUTTON_COUNT) * BUTTON_COUNT;
i += BUTTON_COUNT) {
result += pushRequired *
subVectorSum(descendingFrequency, i, i + BUTTON_COUNT);
pushRequired++;
}
// residual
for (; i < descendingFrequency.size(); i++) {
result += pushRequired * descendingFrequency[i];
}
return result;
}
private:
static int subVectorSum(const vector<int>& vec, size_t begin, size_t end)
{
end = min(vec.size(), end);
return accumulate(
next(vec.begin(), begin),
next(vec.begin(), end),
0);
}
};