Hướng dẫn giải của Mã số sức khỏe (Đề HSG Quảng Bình 2021)
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
Những người có cùng mã số là những người đã tiếp xúc với nhau. Vậy người không tiếp xúc với ai là người có mã số chỉ xuất hiện đúng một lần. Ta cần tìm trong các mã số đó mã nhỏ nhất và in ra chỉ số của người mang mã đó (nếu không có thì in -1).
Sub 1: Vét cạn — ~O(N^2)~
Với mỗi người i, duyệt toàn bộ dãy để đếm số người có cùng mã a[i]. Nếu đếm được đúng 1 (chỉ có chính người đó) và mã nhỏ hơn mã tốt nhất đang có thì cập nhật đáp án. Đúng nhưng với N = 2·10^5 thì quá chậm.
Kết quả chấm: đạt 18/25 test (7 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("HEALTH.INP", "r")) { freopen("HEALTH.INP", "r", stdin); freopen("HEALTH.OUT", "w", stdout); }
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
// Vet can: voi moi nguoi i, dem so nguoi j co cung ma so
int ans = -1, bestCode = INT_MAX;
for (int i = 1; i <= n; i++) {
int cnt = 0;
for (int j = 1; j <= n; j++)
if (a[j] == a[i]) cnt++;
// Nguoi i khong tiep xuc ai khi ma so cua i chi xuat hien dung 1 lan
if (cnt == 1 && a[i] < bestCode) {
bestCode = a[i];
ans = i;
}
}
cout << ans << "\n";
return 0;
}
Sub 2: Đếm bằng mảng — ~O(N)~
Mã số không vượt quá N ≤ 2·10^5 nên dùng mảng cnt[v] để đếm số người có mã v ngay khi đọc dữ liệu. Sau đó duyệt một lần: người i thỏa điều kiện khi cnt[a[i]] == 1, và ta giữ người có mã nhỏ nhất. Lưu ý dùng INT_MAX làm giá trị khởi đầu cho mã tốt nhất.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("HEALTH.INP", "r")) { freopen("HEALTH.INP", "r", stdin); freopen("HEALTH.OUT", "w", stdout); }
int n;
cin >> n;
vector<int> a(n + 1);
// cnt[v] = so nguoi co ma so v (1 <= v <= N <= 2*10^5)
vector<int> cnt(200005, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
cnt[a[i]]++;
}
// Tim ma so nho nhat ma chi co dung 1 nguoi mang no; in chi so cua nguoi do
int ans = -1, bestCode = INT_MAX;
for (int i = 1; i <= n; i++) {
if (cnt[a[i]] == 1 && a[i] < bestCode) {
bestCode = a[i];
ans = i;
}
}
cout << ans << "\n";
return 0;
}
Bình luận