A23490. 积木小X在地上玩积木，每块积木都是一个1*1*1的立方体。地面可以看成一个n*m的网格，其中每一小格内部整齐地从下到上堆着若干块积木。其中第i行第j列中有h[i][j]块积木。现在小X想要拿走一些积木，使得剩下来到积木组成一个正立方体，正立方体指的是长宽高都相同的立方体。小X想问你他最少拿掉多少块积木才能使得最后剩下来到积木组成一个正立方体。输入第一行，2个整数n和m表示地面的大小。接下来n行，…
填空题
较难
知识点
题目描述
积木
小X在地上玩积木，每块积木都是一个1*1*1的立方体。地面可以看成一个n*m的网格，其中每一小格内部整齐地从下到上堆着若干块积木。其中第i行第j列中有h[i][j]块积木。
现在小X想要拿走一些积木，使得剩下来到积木组成一个正立方体，正立方体指的是长宽高都相同的立方体。
小X想问你他最少拿掉多少块积木才能使得最后剩下来到积木组成一个正立方体。
输入
第一行，2个整数n和m表示地面的大小。
接下来n行，每行m个非负整数。第i行第j个数表示h[i][j]。
输出
一行一个整数表示答案。
样例输入1
3
3
2 2 1
3 2 2
3 1 2样例输入2
5
5
4 4 3 4 3
3 4 3 3 3
3 3 1 4 4
3 4 4 3 3
4 3 4 4 4样例输出1
10样例输出2
77提示
样例解释1
拿完之后每个位置的积木数为：
2 2 0
2 2 0
0 0 0
一共拿掉(2-2)+(2-2)+(1-0)+(3-2)+(2-2)+(2-0)+(3-0)+(1-0)+(2-0)=1+1+2+3+1+2=10块积木。
数据范围
对于所有测试点 1<=n,m<=1000, 0<=h[i][j]<=1000
对于测试点1-3 ：1<=n,m<=50
对于测试点4-6 ：1<=n,m<=200
对于测试点7-9 ：1<=n,m<=1000, 0<=h[i][j]<=20
对于测试点10-12 ：1<=n,m<=1000
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> h(n, vector<int>(m));
vector<int> all; // 收集所有高度
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> h[i][j];
all.push_back(h[i][j]);
}
}
sort(all.begin(), all.end());
int total = n * m; // 地面总格子数
long long min_remove = 1e18;
// 枚举可能的立方体边长k（k^3 <= 总积木数）
for (int k = 0; k * k * k <= (long long)n * m * 1000; ++k) {
int required = k * k * k; // 立方体体积
if (required == 0) { // 全拿走
min_remove = 0;
continue;
}
if (k > n || k > m) continue; // 边长超过地面尺寸
// 前k*k个最大的高度中，取第k*k个作为基准h（保证至少k^3个积木）
int take = k * k; // 地面需要k×k个格子
if (take > all.size()) continue;
int h_max = all[all.size() - take]; // 第take大的高度
// 计算总积木数是否足够
long long sum = 0;
for (int x : all) {
sum += min(x, h_max);
}
if (sum >= required) {
// 计算需要移除的数量
long long remove = sum - required;
if (remove < min_remove) {
min_remove = remove;
}
}
}
cout << min_remove << endl;
return 0;
}
上一题
下一题