Hướng dẫn giải của Đu lít contest
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ính điểm và thời gian làm bài của 2 người chơi trong một cuộc thi 1v1. Mỗi người có n bài làm. Với mỗi bài: nếu làm đúng (thời gian > 0) thì được cộng 10 điểm và cộng dồn thời gian làm bài; nếu sai (thời gian = 0) thì không được điểm và không cộng thời gian. Quy tắc thắng: so sánh điểm trước, nếu bằng thì so sánh thời gian (người nào tổng thời gian ít hơn thì thắng), nếu vẫn bằng thì hòa (in 'Double Win').
Các cách tiếp cận
Cách Xử lý trực tiếp (Direct Processing)
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
long long time1 = 0, time2 = 0;
int score1 = 0, score2 = 0;
// Đọc và xử lý ngay lập tức để tiết kiệm bộ nhớ
for (int i = 0; i < n; i++) {
int t;
cin >> t;
if (t > 0) {
score1 += 10;
time1 += t;
}
}
for (int i = 0; i < n; i++) {
int t;
cin >> t;
if (t > 0) {
score2 += 10;
time2 += t;
}
}
// So sánh điểm
if (score1 > score2) {
cout << "1";
} else if (score2 > score1) {
cout << "2";
} else {
// Điểm bằng, so sánh thời gian
if (time1 < time2) {
cout << "1";
} else if (time2 < time1) {
cout << "2";
} else {
cout << "Double Win";
}
}
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(1)
Đây là cách tiếp cận trực quan và hiệu quả nhất. Thay vì lưu trữ toàn bộ mảng, ta chỉ cần đọc giá trị và cập nhật điểm số cùng thời gian ngay lập tức. Với mỗi người, ta đọc n số nguyên, kiểm tra nếu thời gian > 0 thì cộng 10 điểm và cộng vào tổng thời gian. Cuối cùng, so sánh điểm trước, nếu hòa thì so sánh thời gian. Cách này tối ưu về cả thời gian và bộ nhớ vì không cần lưu mảng.
Cách Lưu mảng và xử lý sau (Array Storage)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
// Khai báo mảng có kích thước cố định lớn
const int MAX = 1e7 + 5;
int a[MAX], b[MAX];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
long long time1 = 0, time2 = 0;
int score1 = 0, score2 = 0;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
score1 += 10;
time1 += a[i];
}
if (b[i] > 0) {
score2 += 10;
time2 += b[i];
}
}
if (score1 > score2) {
cout << "1";
} else if (score2 > score1) {
cout << "2";
} else {
if (time1 < time2) {
cout << "1";
} else if (time2 < time1) {
cout << "2";
} else {
cout << "Double Win";
}
}
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Cách này đọc và lưu toàn bộ dữ liệu vào mảng trước, sau đó mới xử lý. Dễ hiểu hơn nhưng tốn bộ nhớ O(n) để lưu hai mảng. Với n lên tới 10^7, cách này có thể gây tràn bộ nhớ stack nếu khai báo mảng thường; cần khai báo mảng toàn cục hoặc dùng vector. Logic tính điểm và thời gian tương tự cách 1.
Cách Sử dụng vector động (Dynamic Vector)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
vector<int> b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
long long time1 = 0, time2 = 0;
int score1 = 0, score2 = 0;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
score1 += 10;
time1 += a[i];
}
if (b[i] > 0) {
score2 += 10;
time2 += b[i];
}
}
if (score1 > score2) {
cout << "1";
} else if (score2 > score1) {
cout << "2";
} else {
if (time1 < time2) {
cout << "1";
} else if (time2 < time1) {
cout << "2";
} else {
cout << "Double Win";
}
}
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Tương tự cách lưu mảng nhưng dùng vector để linh hoạt hơn về bộ nhớ. Tuy nhiên, với n lớn (10^7), việc cấp phát động nhiều có thể chậm hơn mảng toàn cục. Logic tính điểm và thời gian vẫn giữ nguyên. Đây là cách phổ biến trong lập trình thi đấu nhưng không tối ưu bằng cách xử lý trực tiếp.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n) | O(1) | Xử lý trực tiếp (Direct Processing) |
| 2 | O(n) | O(n) | Lưu mảng và xử lý sau (Array Storage) |
| 3 | O(n) | O(n) | Sử dụng vector động (Dynamic Vector) |
Bài học kinh nghiệm
- Quy tắc thắng ưu tiên điểm số trước, thời gian chỉ dùng để phá hòa.
- Thời gian chỉ được cộng khi làm đúng (> 0), sai (0) thì không ảnh hưởng.
- Xử lý trực tiếp khi đọc input là tối ưu nhất về bộ nhớ (O(1))
Lỗi thường gặp
- Quên kiểm tra điều kiện thời gian > 0 trước khi cộng điểm và thời gian.
- Tràn bộ nhớ khi khai báo mảng lớn (10^7 phần tử) trên stack; cần dùng mảng toàn cục hoặc vector.
- So sánh sai thứ tự: phải so sánh điểm trước, thời gian sau.
- Dùng int cho tổng thời gian có thể tràn số (với n=10^7 và mỗi phần tử lên tới 10^9, tổng có thể lên tới 10^16), cần dùng long long.
Bình luận