形式M组具有与N个建筑物等高的建筑物
形式M组具有与N个建筑物等高的建筑物
提问于 2016-12-09 20:40:15
我已经得到了N个建筑物的高度。
我必须组成大小为M的小组，具有相同高度的建筑物。给定的情况下，我可以摧毁较高的建筑物，使其高度与较小的建筑物相等。
我必须找到要摧毁的建筑物的最小数目，以便恰好形成N/M groups.Given，N总是可以被M整除。
例如：
N=8，M=4
建筑物高度:6 4 5 1 5 2 3 2
答案:5
我们可以摧毁两个高度为5的建筑物到两个高度为2的建筑物形成第一组，然后摧毁高度为3、4、6的建筑物到高度1，形成具有相同高度1的建筑物的第二组。
因此，我们组成2(N/M)组，大小为4(M).Minimum要摧毁的建筑物数量为5。
N=8，M=4
建筑物高度:1 1 1 2 4 4 4
答案:1
谁能在这方面给我一些提示。
回答 1
Stack Overflow用户
发布于 2016-12-09 21:35:58
算法
- 将所有的高度(升序)放入一个散列中(比如STL上的有序映射)- key作为高度，数据作为该高度的频率。
- 对于N/M次，获取频率(比如和)并继续相加。
- =N-sum。
伪码
arr[] = {6 4 5 1 5 2 3 2}
map<int, int, greater<int>> mp;
for(auto elem : arr)
{
if(data exist)
increase freq
else
insert key with freq as 1.
}
sum = 0
for(i=0 to N/M)
sum += freq of mp[i]
Result = N - sum页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/41060726
复制相关文章
相似问题
腾讯云开发者
