Hướng dẫn giải của th_máy bán hàng tự động
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm số xuất hiện nhiều nhất trong một dãy số và tần suất xuất hiện của nó. Nếu có nhiều số có cùng tần suất xuất hiện cao nhất, ta cần chọn số có giá trị nhỏ nhất. Input bao gồm số nguyên n và dãy n số nguyên. Output là số có tần suất cao nhất và tần suất đó.
Các cách tiếp cận
Cách Sử dụng map (đếm tần suất)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
map<long long, int> freq;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
freq[x]++;
}
long long best_val = 0;
int best_freq = 0;
for (auto p : freq) {
if (p.second > best_freq) {
best_freq = p.second;
best_val = p.first;
}
}
cout << best_val << ' ' << best_freq;
return 0;
}
- Time Complexity: O(n log n)
- Space Complexity: O(n)
Sử dụng std::map để đếm tần suất của từng số. Map tự động sắp xếp các khóa theo thứ tự tăng dần. Khi duyệt qua map, ta ưu tiên cập nhật khi tần suất lớn hơn, do đó nếu có nhiều số cùng tần suất cao nhất, số xuất hiện trước (nhỏ hơn) sẽ được chọn.
Cách Mảng đếm (Frequency Array)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6 + 7;
int f[MAX];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
f[x]++;
}
int res = 1, mx = 0;
for (int i = 1; i < MAX; i++) {
if (f[i] > mx) {
mx = f[i];
res = i;
}
}
cout << res << ' ' << mx;
return 0;
}
- Time Complexity: O(n + MAX)
- Space Complexity: O(MAX)
Sử dụng mảng đếm cố định với kích thước đủ lớn để lưu tần suất. Duyệt từ 1 đến MAX để tìm số có tần suất lớn nhất. Vì duyệt từ nhỏ đến lớn, số có giá trị nhỏ hơn sẽ được ưu tiên chọn nếu cùng tần suất.
Cách Cập nhật trong lúc nhập (Optimized)
#include <fstream>
#include <map>
using namespace std;
int main() {
ifstream in("BAI2.INP");
ofstream out("BAI2.OUT");
int n;
in >> n;
map<long long, long long> mp;
long long max_freq = 0;
for (int i = 0; i < n; i++) {
long long tmp;
in >> tmp;
mp[tmp]++;
if (mp[tmp] > max_freq) {
max_freq = mp[tmp];
}
}
for (auto x : mp) {
if (x.second == max_freq) {
out << x.first << " " << x.second;
break;
}
}
in.close();
out.close();
return 0;
}
- Time Complexity: O(n log n)
- Space Complexity: O(n)
Cập nhật tần suất cao nhất ngay trong lúc nhập. Sau đó duyệt map (tự động tăng dần) để tìm số đầu tiên có tần suất bằng max_freq. Cách này đảm bảo chọn được số nhỏ nhất có tần suất cao nhất.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n log n) | O(n) | Sử dụng map (đếm tần suất) |
| 2 | O(n + MAX) | O(MAX) | Mảng đếm (Frequency Array) |
| 3 | O(n log n) | O(n) | Cập nhật trong lúc nhập (Optimized) |
Bài học kinh nghiệm
- Sử dụng map hoặc mảng đếm để đếm tần suất hiệu quả
- Duyệt theo thứ tự tăng dần để tự động chọn số nhỏ hơn khi có cùng tần suất
- Có thể tối ưu bằng cách cập nhật max_freq ngay trong vòng lặp nhập
Lỗi thường gặp
- Quên xử lý trường hợp nhiều số cùng tần suất cao nhất
- Sử dụng mảng đếm quá nhỏ导致 overflow
- Không tối ưu I/O cho dữ liệu lớn
Bình luận