Hướng dẫn giải của Trao 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.
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
, , ,
Editorial for traogiai: Trao giải
Hiểu bài toán
Bài toán yêu cầu tính số lượng học sinh được trao giải theo quy tắc: đầu tiên chọn ra [n/2] học sinh có điểm số cao nhất (sau khi sắp xếp giảm dần), sau đó chọn thêm tất cả những học sinh có điểm số bằng với học sinh có điểm số thấp nhất trong số [n/2] học sinh đã chọn ban đầu. Nói cách khác, nếu điểm số của học sinh ở vị trí [n/2] (tính từ 0) là X, thì tất cả học sinh có điểm số X đều được trao giải.
Các cách tiếp cận
Cách Sắp xếp và đếm
#include <stdio.h>
#include <stdlib.h>
// Hàm so sánh để sắp xếp giảm dần
int cmp(const void *a, const void *b) {
return (*(int*)b - *(int*)a);
}
int main() {
int n;
scanf("%d", &n);
int d[n];
for(int i = 0; i < n; i++) {
scanf("%d", &d[i]);
}
// Sắp xếp mảng điểm giảm dần
qsort(d, n, sizeof(int), cmp);
// Số lượng học sinh chọn ban đầu
int limit = n / 2;
int count = limit;
// Điểm chuẩn để được chọn thêm
int min_score = d[limit - 1];
// Đếm thêm những người có điểm bằng điểm chuẩn
for(int i = limit; i < n; i++) {
if(d[i] == min_score) {
count++;
}
}
printf("%d\n", count);
return 0;
}
- Time Complexity: O(n log n)
- Space Complexity: O(n)
Cách tiếp cận đơn giản nhất là sử dụng hàm sắp xếp có sẵn (qsort). Đầu tiên, ta sắp xếp mảng điểm số theo thứ tự giảm dần. Sau đó, ta xác định điểm số của người được chọn cuối cùng trong top [n/2] (đây là giá trị tại chỉ số [n/2] - 1). Cuối cùng, ta đếm tổng số người có điểm số bằng hoặc cao hơn ngưỡng này. Lưu ý: thay vì đếm từ đầu, ta chỉ cần đếm số người trong top [n/2] (là [n/2]) cộng với số người còn lại có điểm bằng điểm chuẩn.
Cách Tối ưu với Hash Map (Đếm tần suất)
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
map<int, int, greater<int>> score_counts;
for (int i = 0; i < n; i++) {
int score;
cin >> score;
score_counts[score]++;
}
int target = n / 2;
int count = 0;
int cutoff_score = 0;
bool found_cutoff = false;
// Duyệt qua các điểm số từ cao đến thấp
for (auto const& [score, freq] : score_counts) {
if (count + freq >= target) {
cutoff_score = score;
found_cutoff = true;
break;
}
count += freq;
}
// Tính tổng số người được giải
int total_winners = 0;
for (auto const& [score, freq] : score_counts) {
if (score > cutoff_score) {
total_winners += freq;
} else if (score == cutoff_score) {
total_winners += freq;
break;
}
}
cout << total_winners << endl;
return 0;
}
- Time Complexity: O(n log n)
- Space Complexity: O(n)
Phương pháp này sử dụng cấu trúc map (hoặc unordered_map) để đếm tần suất các điểm số. Ưu điểm là nó tự động sắp xếp các điểm số giảm dần (nếu dùng std::map với greater). Cách này có thể hiệu quả hơn nếu số lượng điểm số trùng lặp nhiều, nhưng về độ phức tạp vẫn là O(n log n) do thao tác với map. Tuy nhiên, trong bài toán này, giải pháp sắp xếp trực tiếp mảng số nguyên thường nhanh và dễ implement hơn.
Cách Sử dụng Counting Sort (Nhanh nhất)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
// Giả sử điểm số tối đa là 10^6 theo đề bài
const int MAX_SCORE = 1000001;
vector<int> freq(MAX_SCORE, 0);
int max_score = 0;
for (int i = 0; i < n; i++) {
int score;
cin >> score;
freq[score]++;
if (score > max_score) max_score = score;
}
int target = n / 2;
int count = 0;
int cutoff_score = 0;
// Duyệt từ điểm cao nhất trở xuống
for (int s = max_score; s >= 0; s--) {
if (freq[s] == 0) continue;
if (count + freq[s] >= target) {
cutoff_score = s;
break;
}
count += freq[s];
}
// Tính tổng số người được giải
// Bao gồm tất cả người có điểm > cutoff_score và người có điểm == cutoff_score
int total_winners = 0;
for (int s = max_score; s > cutoff_score; s--) {
total_winners += freq[s];
}
total_winners += freq[cutoff_score];
cout << total_winners << endl;
return 0;
}
- Time Complexity: O(n + K) (K = 10^6)
- Space Complexity: O(K) (K = 10^6)
Vì giới hạn điểm số khá nhỏ (10^6) và n lớn (10^5), ta có thể dùng Counting Sort (thường gọi là thuật toán đếm). Ta tạo một mảng tần suất kích thước 10^6, đếm số lần xuất hiện của từng điểm số. Sau đó, ta duyệt từ điểm cao nhất xuống thấp để tìm ra điểm số chuẩn (cutoff score). Phương pháp này có độ phức tạp thời gian tuyến tính O(n + K), nhanh hơn đáng kể so với O(n log n) khi n lớn.
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ắp xếp và đếm |
| 2 | O(n log n) | O(n) | Tối ưu với Hash Map (Đếm tần suất) |
| 3 | O(n + K) (K = 10^6) | O(K) (K = 10^6) | Sử dụng Counting Sort (Nhanh nhất) |
Bài học kinh nghiệm
- Vấn đề cốt lõi là xác định giá trị 'ngưỡng' (cutoff score) - là điểm số của học sinh ở vị trí [n/2] sau khi sắp xếp giảm dần.
- Mọi học sinh có điểm số >= ngưỡng đều được trao giải.
- Có thể giải quyết bằng cách sắp xếp (đơn giản, dễ hiểu) hoặc đếm tần suất (nhanh hơn về lý thuyết).
Lỗi thường gặp
- Sai lệch khi tính chỉ số mảng: Nếu dùng mảng 0-based, học sinh đầu tiên được chọn ở vị trí [n/2] - 1 sau khi sắp xếp.
- Lầm tưởng giữa việc chọn chính xác [n/2] người và chọn thêm người bằng điểm: Cần cộng số người bằng điểm vào số lượng ban đầu, không thay đổi.
- Quên trường hợp tất cả học sinh có điểm số bằng nhau.
Bình luận
ko hieu