Hướng dẫn giải của Luyện tập (đề Đồng Tháp 2021)
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
Cần tìm số lần xuất hiện lớn nhất của một giá trị thời gian trong dãy a gồm n số (n ≤ 10^5). Đây chính là tìm tần suất lớn nhất (mode) của dãy.
Sub 1: Vét cạn — ~O(n^2)~
Với mỗi bài i, duyệt toàn bộ dãy để đếm số bài có thời gian bằng a[i], rồi lấy đếm lớn nhất. Đúng nhưng với n = 10^5 thì chậm.
Kết quả chấm: đạt 15/20 test (5 test còn lại quá giờ, không sai).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("LUYENTAP.INP", "r")) { freopen("LUYENTAP.INP", "r", stdin); freopen("LUYENTAP.OUT", "w", stdout); }
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Vet can: voi moi bai i, dem so bai j co cung thoi gian a[j] == a[i]
int best = 0;
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < n; j++)
if (a[j] == a[i]) cnt++;
best = max(best, cnt);
}
cout << best << "\n";
return 0;
}
Sub 2: Sắp xếp rồi đếm đoạn bằng nhau — ~O(n \log n)~
Sắp xếp dãy để các giá trị bằng nhau nằm liền nhau. Sau đó duyệt, mỗi đoạn liên tiếp có cùng giá trị là một nhóm, và độ dài lớn nhất của nhóm là đáp án. Dùng long long cho thời gian dù giá trị tối đa chỉ 10^7.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("LUYENTAP.INP", "r")) { freopen("LUYENTAP.INP", "r", stdin); freopen("LUYENTAP.OUT", "w", stdout); }
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Sap xep de cac thoi gian bang nhau nam lien tiep nhau
sort(a.begin(), a.end());
int best = 0;
// Dem do dai moi doan lien tiep co cung gia tri
for (int i = 0; i < n;) {
int j = i;
while (j < n && a[j] == a[i]) j++;
best = max(best, j - i);
i = j;
}
cout << best << "\n";
return 0;
}
Bình luận