R0011. 「T1」积木高塔 Solution

返回题目

简要题意：

给定一个矩阵，以及其每一格中完全相同立方体的高度（即个数），求：

1. 这座高塔最高点的高度。
2. 这座高塔从第 $1$ 层到最高层之间，每一层的立方体个数。

题目分析：

做法 $1$:

期望得分：$50\ pts$

对于层数，我们可以在读入时使用 max 函数取得最高层，也就是求出了总层数。然后对于每一层，都扫描一遍，如果积木柱高度大于等于这一层的高度，就说明这个积木柱在这个层数有一格积木，故 cnt++。

时间复杂度：$\mathcal{O}(nmk)$

$\mathrm{Code:}$

//Code by Polarie，略有修改
#include <bits/stdc++.h>
using namespace std;
int a[10001][10001];

int main () {
	int n, m, maxn = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			maxn = max(maxn, a[i][j]);//取最大值
		}
	}
	cout << maxn << endl;
	for (int i = 1; i <= maxn; i++) {
		int cnt = 0;//归零
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= m; k++) {
				if (a[j][k] >= i)
					cnt++;//扫描
			}
		}
		cout << cnt << endl;
	}
	return 0;//好习惯
}

然鹅 $\mathrm{Subtask\ 3}$ 全部 $\mathrm{TLE}$……

做法 $2$:

期望得分：$100\ pts$

既然要统计积木个数，那我们就考虑计数排序，利用了桶排的思想，这样的好处是不用扫描，且不用存储矩阵，即少开了一个 $5000 \times 5000$ 的二维数组。

时间复杂度：$\mathcal{O}(nm)$

$\mathrm{Code:}$

//Code by __er
#include <bits/stdc++.h>
using namespace std;
int maxn = -1, n, m, i, j, ans[11]/*桶*/, tmp;

inline int read() {//快速读入
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
		x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}

int main() {
	n = read();
	m = read();
	int nm = n * m;
	ans[1] = nm;//所有积木柱高度都大于1，故第一层必然全都有
	for (i = 1; i <= nm; i++) {
		tmp = read();
		maxn = max(maxn, tmp);
		while (tmp >= 2) {
			ans[tmp]++;
			tmp--;//统计
		}
	}
	cout << maxn << endl;
	for (i = 1; i <= maxn; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}

不开 $O2$ 最慢一个点也在 $600ms$ 以下，足以通过此题。