Bardisk 和 Barisore 喜欢玩 Minecraft。这天 Bardisk 收集了 n种建筑方块,第i 种建筑方块有 u[i] 个,Bardisk 想把这些方块铺成一个宽度为k 的长方形,起初他把相似的方块铺在一起,但是 Barisore 嫌太丑了,她要求每行(即沿着宽度的方向)的 k个方块种类都是不同的。 Bardisk 是建筑白痴,所以他想问问聪明的你,使用现有的材料,他最多可以按这样的要求铺多少行? 输入格式 第一行两个正整数 ,意义如题。 第二行 个正整数,表示序列 ,意义如题。 输出格式 输出一个正整数,表示答案。 样例 输入 6 5 1 9 1 9 8 6 输出 2 数据范围与提示 本题考察贪心和二分。 样例解释 一共可以堆两行,第一行选择第 1、2、4、5、6 种方块各一个,第二行选择第 2、3、4、5、6 种方块各一个,这之后只剩下四种方块了,无法堆出新的一行,故答案为 。 c++代码
时间: 2024-04-09 14:28:20 浏览: 100
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> blocks(n);
for (int i = 0; i < n; i++) {
cin >> blocks[i];
}
sort(blocks.begin(), blocks.end(), greater<int>());
int ans = 0;
int rows = 0;
for (int i = 0; i < n; i++) {
rows += blocks[i] / k;
if (rows >= k) {
ans += k;
rows -= k;
}
else {
ans += rows;
rows = 0;
}
}
cout << ans << endl;
return 0;
}
```
相关问题
Bardisk 和 Barisore 喜欢玩 Minecraft。这天 Bardisk 收集了n 种建筑方块,第i种建筑方块有u[i]个,Bardisk 想把这些方块铺成一个宽度为k的长方形,起初他把相似的方块铺在一起,但是 Barisore 嫌太丑了,她要求每行(即沿着宽度的方向)的 k个方块种类都是不同的。 Bardisk 是建筑白痴,所以他想问问聪明的你,使用现有的材料,他最多可以按这样的要求铺多少行?
这个问题可以使用贪心算法来解决。
首先,我们可以统计每种建筑方块的数量,并将它们按照数量从大到小进行排序。
接下来,我们可以从最多数量的建筑方块开始,依次选择一个方块放入长方形中的每一行。在选择方块时,我们需要确保当前行的方块种类与上一行不同。
具体的步骤如下:
1. 将建筑方块按照数量从大到小进行排序。
2. 初始化计数器count为0,表示当前已经铺设的行数。
3. 遍历排序后的建筑方块列表,对于每个方块:
- 如果方块的数量为0,则跳过。
- 否则,将当前行数count加1,将该方块的数量减1,并将该方块种类放入当前行。
- 如果当前行数count等于宽度k,则重置count为0。
- 继续遍历下一个方块。
4. 返回最终的行数count。
通过以上贪心算法,我们可以得到按要求铺设的最大行数。希望这个解决方案能对你有所帮助!
阅读全文