Hiểu bài toán

Bài toán yêu cầu tìm ra đội thi có thành tích cao nhất trong một kỳ thi đồng đội. Mỗi đội có n thành viên và mỗi thành viên giải m bài toán. Nếu một bài toán được giải (thời gian > 0), đội được cộng 10 điểm và cộng thêm thời gian giải bài đó vào tổng thời gian của đội. Thứ tự ưu tiên xếp hạng:

1. Điểm số cao hơn.
2. Nếu hòa điểm, tổng thời gian ít hơn.
3. Nếu vẫn hòa, chọn đội có số hiệu (ID) nhỏ hơn. Đầu vào: Số đội (n), số bài (m), ma trận thời gian giải bài của n đội. Đầu ra: In ra số hiệu của đội chiến thắng.

Các cách tiếp cận

Cách Duyệt tuần tự và tối ưu hóa

#include <bits/stdc++.h>
using namespace std;

struct Team {
    int id;
    int score;
    int time;
};

int main() {
    ifstream fin("TEAM.INP");
    ofstream fout("TEAM.OUT");

    int n, m;
    fin >> n >> m;

    int best_id = -1;
    int best_score = -1;
    int best_time = INT_MAX;

    for (int i = 1; i <= n; ++i) {
        int current_score = 0;
        int current_time = 0;

        for (int j = 0; j < m; ++j) {
            int x;
            fin >> x;
            if (x > 0) {
                current_score += 10;
                current_time += x;
            }
        }

        // So sánh với đội hiện tại
        // 1. So sánh điểm
        if (current_score > best_score) {
            best_score = current_score;
            best_time = current_time;
            best_id = i;
        } 
        // 2. Nếu hòa điểm, so sánh thời gian
        else if (current_score == best_score) {
            if (current_time < best_time) {
                best_time = current_time;
                best_id = i;
            }
            // 3. Nếu hòa thời gian, so sánh ID (ID nhỏ hơn ưu tiên)
            else if (current_time == best_time) {
                if (i < best_id) {
                    best_id = i;
                }
            }
        }
    }

    fout << best_id;
    return 0;
}

• Time Complexity: O(n * m)
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu nhất và hiệu quả bộ nhớ nhất. Thay vì lưu trữ thông tin của tất cả các đội vào mảng/struct rồi mới xử lý, ta chỉ cần duy nhất một biến để lưu thông tin của đội đang dẫn đầu (bestscore, besttime, best_id). Trong quá trình đọc dữ liệu từng đội, ta tính ngay điểm và thời gian của đội đó, sau đó so sánh ngay với đội đang dẫn đầu để cập nhật. Cách này giúp tiết kiệm bộ nhớ đáng kể (chỉ cần O(1) bộ nhớ bổ sung) và thường nhanh hơn do tránh được bước duyệt lại toàn bộ dữ liệu.

Cách Lưu trữ vào cấu trúc rồi sắp xếp

#include <bits/stdc++.h>
using namespace std;

struct Team {
    int id;
    int score;
    int time;
};

bool cmp(const Team &a, const Team &b) {
    if (a.score != b.score) return a.score > b.score;
    if (a.time != b.time) return a.time < b.time;
    return a.id < b.id;
}

int main() {
    ifstream fin("TEAM.INP");
    ofstream fout("TEAM.OUT");

    int n, m;
    fin >> n >> m;

    vector<Team> teams(n);

    for (int i = 0; i < n; ++i) {
        teams[i].id = i + 1;
        teams[i].score = 0;
        teams[i].time = 0;

        for (int j = 0; j < m; ++j) {
            int x;
            fin >> x;
            if (x > 0) {
                teams[i].score += 10;
                teams[i].time += x;
            }
        }
    }

    sort(teams.begin(), teams.end(), cmp);

    fout << teams[0].id;

    return 0;
}

• Time Complexity: O(n * m + n log n)
• Space Complexity: O(n)

Cách tiếp cận này sử dụng một vector để lưu trữ thông tin của tất cả các đội. Sau khi nhập dữ liệu và tính toán điểm số, ta sử dụng hàm sort với hàm so sánh自定义 (cmp) để sắp xếp lại danh sách các đội theo tiêu chí đề bài. Đội đứng đầu tiên sau khi sắp xếp chính là đội chiến thắng. Phương pháp này dễ hiểu và dễ code, nhưng tốn bộ nhớ hơn (O(n)) và chậm hơn một chút so với phương pháp duyệt trực tiếp do chi phí cho việc sắp xếp.

Cách Duyệt trực tiếp (Code ngắn)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ifstream fin("TEAM.INP");
    ofstream fout("TEAM.OUT");
    int n, m;
    fin >> n >> m;

    int max_sum = 0, min_time = INT_MAX, winner = 0;

    for(int i = 1; i <= n; i++){
        int sum = 0, time = 0;
        for(int j = 0; j < m; j++){
            int tmp; fin >> tmp;
            if(tmp > 0){
                sum += 10;
                time += tmp;
            }
        }
        // Cập nhật điều kiện
        if(sum > max_sum || (sum == max_sum && time < min_time) || 
           (sum == max_sum && time == min_time && i < winner)) {
            max_sum = sum;
            min_time = time;
            winner = i;
        }
    }
    out << winner;
    return 0;
}

• Time Complexity: O(n * m)
• Space Complexity: O(1)

Đây là biến thể của Approach 1 nhưng viết gọn hơn bằng cách gộp tất cả điều kiện vào một câu lệnh if. Logic vẫn đảm bảo ưu tiên điểm cao nhất, rồi thời gian thấp nhất, rồi ID nhỏ nhất. Đây là cách tiếp cận hiệu quả về cả thời gian và bộ nhớ.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Tiêu chí so sánh (Scoring Criteria) là chìa khóa: Phải xử lý đúng thứ tự ưu tiên: Điểm (cao hơn) -> Thời gian (ít hơn) -> ID (nhỏ hơn).
• Xử lý dữ liệu trực tiếp (Online Processing): Trong bài toán tìm max/min, ta không nhất thiết phải lưu toàn bộ dữ liệu. Ta có thể vừa đọc vừa xử lý để tiết kiệm bộ nhớ (Space Complexity O(1)).
• Kiểu dữ liệu: Điểm số và thời gian chỉ cần int (thời gian thường tính bằng phút, tổng < 10^6).

Lỗi thường gặp

• Lỗi logic điều kiện: Viết sai thứ tự ưu tiên (ví dụ kiểm tra thời gian trước điểm số) sẽ dẫn đến kết quả sai.
• Bỏ qua ID hòa breaker: Nếu chỉ so sánh điểm và thời gian, khi có hai đội cùng điểm và cùng thời gian, code có thể không xác định được đội thắng cuộc theo yêu cầu (chọn ID nhỏ nhất).
• Lỗi nhập xuất: Quên khai báo freopen hoặc ifstream/ofstream dẫn đến lỗi chạy trên máy chấm tự động (đặc biệt trên VNOI hay OJ nước ngoài).