Hướng dẫn giải của Đạt giải (đề KS ĐH 2024)
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 học sinh với điểm Ai (số nguyên, Ai ≤ 20). Tính tbc là trung bình cộng làm tròn lên thành số nguyên, rồi đếm số học sinh có điểm lớn hơn tbc. Với n ≤ 10^5 cần tính tổng một lần.
Sub 1: Vét cạn — ~O(n^2)~
Với mỗi học sinh, tính lại tổng điểm của toàn bộ n học sinh rồi tính tbc, sau đó so sánh. Mỗi lần so sánh đều tốn O(n) nên tổng O(n^2). Đúng nhưng chậm với n lớn.
Kết quả chấm: 15/20 (SUB ok 15/20, TLE 5, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
int dem = 0;
// Vet can: voi moi thi sinh i, tinh lai tong diem tu dau (O(n)) de tinh tbc, roi dem so nguoi duoc giai
// Moi lan so sanh deu tinh lai tbc nen cham O(n^2)
for (int i = 0; i < n; i++) {
long long tong = 0;
for (int j = 0; j < n; j++) tong += a[j];
// tbc lam tron len: (tong + n - 1) / n
long long tbc = (tong + n - 1) / n;
if (a[i] > tbc) dem++;
}
cout << dem << "\n";
return 0;
}
Sub 2: Tính tbc một lần — ~O(n)~
Tính tổng điểm một lần, sau đó tbc = ceil(tổng / n) bằng công thức (tổng + n - 1) / n với số nguyên. Cuối cùng đếm số điểm lớn hơn tbc.
Bẫy: làm tròn lên là ceil, không phải làm tròn thông thường. Ví dụ tổng 48, n = 5 cho 9.6 nên tbc = 10. Dùng long long cho tổng.
Kết quả chấm: 20/20
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
int n;
cin >> n;
vector<long long> a(n);
long long tong = 0;
for (auto &x : a) {
cin >> x;
tong += x;
}
// tbc lam tron len den so nguyen: tinh bang so nguyen (tong + n - 1) / n
long long tbc = (tong + n - 1) / n;
int dem = 0;
for (long long x : a)
if (x > tbc) dem++;
cout << dem << "\n";
return 0;
}
Bình luận