Hướng dẫn giải của [200 đề thầy Đức] Bài 159: Xây dựng tháp
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Mỗi tháp gồm các mẩu gỗ có cùng độ dài, nên chiều cao của một tháp là số mẩu có độ dài đó, và số tháp chính là số độ dài khác nhau. Ta cần tìm chiều cao lớn nhất và số lượng tháp.
Sub 1: Vét cạn — ~O(n^2)~
Với mỗi mẩu gỗ, đếm số mẩu có cùng độ dài bằng cách duyệt cả dãy. Mẩu nào là lần xuất hiện đầu tiên của độ dài đó thì tính thêm một tháp. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
// Vét cạn: mỗi mẫu gỗ i, đếm số mẫu cùng độ dài với nó
int chieuCaoMax = 0, soThap = 0;
for (int i = 0; i < n; i++) {
int dem = 0;
bool laLanDauTien = true; // a[i] có xuất hiện trước đó chưa?
for (int j = 0; j < n; j++) {
if (a[j] == a[i]) dem++;
if (j < i && a[j] == a[i]) laLanDauTien = false;
}
chieuCaoMax = max(chieuCaoMax, dem);
// mỗi độ dài khác nhau tương ứng một tháp
if (laLanDauTien) soThap++;
}
cout << chieuCaoMax << " " << soThap << "\n";
return 0;
}
Sub 2: Đếm bằng mảng — ~O(n + 1000)~
Dùng mảng đếm dem[v] với v <= 1000. Mỗi độ dài khác nhau (dem > 0) là một tháp; chiều cao lớn nhất là giá trị dem lớn nhất. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// dem[v] = số mẫu gỗ có độ dài v (a_i <= 1000)
vector<int> dem(1001, 0);
for (int i = 0; i < n; i++) {
int a;
cin >> a;
dem[a]++;
}
int chieuCaoMax = 0, soThap = 0;
for (int v = 1; v <= 1000; v++) {
if (dem[v] > 0) {
soThap++; // mỗi độ dài là một tháp
chieuCaoMax = max(chieuCaoMax, dem[v]); // chiều cao = số mẫu xếp chồng
}
}
cout << chieuCaoMax << " " << soThap << "\n";
return 0;
}
Bình luận