Hiểu bài toán

Bài toán yêu cầu tính tổng thời gian ba nhân vật Joffrey, Robb và Stannis hoàn thành công việc của họ dựa trên số lượng nhiệm vụ và thời gian mỗi nhiệm vụ. Joffrey hoàn thành n nhiệm vụ, mỗi nhiệm vụ tốn a đơn vị thời gian. Robb hoàn thành m nhiệm vụ, mỗi nhiệm vụ tốn b đơn vị thời gian. Stannis hoàn thành k nhiệm vụ, mỗi nhiệm vụ tốn c đơn vị thời gian. Đầu vào gồm 6 số nguyên n, m, k, a, b, c. ĐẦU RA: In ra tên của nhân vật (hoặc nhiều nhân vật nếu có thời gian bằng nhau) có thời gian hoàn thành lớn nhất. Ví dụ: Nếu Joffrey mất 10, Robb mất 15, Stannis mất 15, đầu ra là 'Robb Stannis'.

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

Cách Tính toán trực tiếp và so sánh

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    freopen("BAI1.inp","r",stdin);
    freopen("BAI1.out","w",stdout);
    int n,m,k,a,b,c;
    cin >> n >> m >> k >> a >> b >> c;
    int mx = max(n * a,max(m * b,k * c));
    if (mx == n * a) cout << "Joffrey ";
    if (mx == m * b) cout << "Robb ";
    if (mx == k * c) cout << "Stannis ";
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Phương pháp này tính toán thời gian cho từng người (Joffrey: na, Robb: mb, Stannis: k*c). Sau đó, nó tìm giá trị lớn nhất trong ba giá trị này. Cuối cùng, nó kiểm tra từng người để xem ai có thời gian bằng với giá trị lớn nhất đó và in tên ra. Cách tiếp cận này rất trực quan và hiệu quả về mặt thời gian.

Cách Sử dụng mảng và vòng lặp

#include <fstream>
using namespace std;

int main() {
    ifstream in("BAI1.INP");
    ofstream out("BAI1.OUT");
    long long n,m,k,a,b,c;
    long long arr[3];
    string name[3] = {"Joffrey","Robb","Stannis"};
    in>>n>>m>>k>>a>>b>>c;
    arr[0] = n*a;
    arr[1] = m*b;
    arr[2] = k*c;
    long long max = arr[0];
    for(int i = 1;i<3;i++) {
        if(arr[i]>max) {
            max = arr[i];
        }
    }
    for(int i = 0;i<3;i++) {
        if(arr[i] == max) {
            out<<name[i]<<" ";
        }
    }
    in.close();
    out.close();
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Cách tiếp cận này lưu trữ thông tin vào một mảng (mảng arr chứa thời gian và mảng name chứa tên). Nó sử dụng một vòng lặp để tìm giá trị lớn nhất trong mảng thời gian. Sau đó, nó lặp lại mảng để in ra tên của những người có thời gian bằng giá trị lớn nhất. Cách này có thể dễ mở rộng nếu có nhiều hơn 3 người.

Cách Xử lý in ra nhiều người (Logic điều kiện)

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

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

    int n, m, k, a, b, c;
    fin >> n >> m >> k >> a >> b >> c;

    int timeJ = n * a;
    int timeR = m * b;
    int timeS = k * c;

    int maxTime = max(timeJ, max(timeR, timeS));

    bool printed = false;

    if (timeJ == maxTime) {
        fout << "Joffrey";
        printed = true;
    }
    if (timeR == maxTime) {
        if (printed) fout << " ";
        fout << "Robb";
        printed = true;
    }
    if (timeS == maxTime) {
        if (printed) fout << " ";
        fout << "Stannis";
    }

    fin.close();
    fout.close();

    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là cách tiếp cận chi tiết nhất trong các giải pháp được cung cấp. Nó tính toán thời gian cho từng người, tìm giá trị lớn nhất sau đó sử dụng các câu lệnh điều kiện if riêng biệt cho từng người. Biến printed được sử dụng để kiểm tra xem đã in tên người nào chưa, từ đó quyết định có in thêm dấu cách trước tên tiếp theo hay không. Điều này đảm bảo định dạng đầu ra chính xác (không có dấu cách thừa ở cuối).

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

Bài học kinh nghiệm

• Bài toán chỉ cần tính toán đơn giản phép nhân và so sánh giá trị.
• Đầu ra có thể bao gồm nhiều tên nếu có cùng thời gian làm việc lớn nhất.
• Sử dụng biến cờ hoặc logic điều kiện cẩn thận để xử lý việc in nhiều tên sao cho không có dấu cách thừa.

Lỗi thường gặp

• Quên kiểm tra các trường hợp hòa (tie) và chỉ in ra một người đầu tiên tìm thấy.
• In ra dấu cách thừa ở cuối dòng đầu ra.
• Sử dụng kiểu dữ liệu quá nhỏ (ví dụ: int thay vì long long) nếu các giá trị đầu vào rất lớn, dẫn đến tràn số.