Hướng dẫn giải của [200 đề thầy Đức] Bài 162: Người hâm mộ

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.

Hướng dẫn giải

Sắp xếp người hâm mộ theo điểm giảm dần, cùng điểm thì theo tên từ điển tăng dần, rồi lấy T người đầu tiên.

Sub 1: Vét cạn chọn dần — ~O(N · T)~

Mỗi lần quét cả danh sách để chọn người "tốt nhất" còn lại, làm T lần. Đạt 14/21 test, còn lại quá giờ.

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

struct NguoiHamMo {
    string ten;
    long long diem;
};

// Ưu tiên: điểm cao hơn trước; cùng điểm thì tên nhỏ hơn (từ điển) trước
bool uuTien(const NguoiHamMo &x, const NguoiHamMo &y) {
    if (x.diem != y.diem) return x.diem > y.diem;
    return x.ten < y.ten;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, T;
    cin >> N >> T;
    string line;
    getline(cin, line);  // bỏ phần còn lại của dòng đầu

    vector<NguoiHamMo> ds(N);
    for (int i = 0; i < N; i++) {
        getline(cin, line);
        while (!line.empty() && (line.back() == '\r' || line.back() == ' ')) line.pop_back();
        size_t p = line.find_last_of(' ');   // token cuối là điểm
        string ten = line.substr(0, p);
        while (!ten.empty() && ten.back() == ' ') ten.pop_back();
        ds[i].ten = ten;
        ds[i].diem = stoll(line.substr(p + 1));
    }

    // Vét cạn: chọn lần lượt người "tốt nhất" còn lại, làm T lần
    vector<bool> used(N, false);
    for (int t = 0; t < T; t++) {
        int best = -1;
        for (int i = 0; i < N; i++)
            if (!used[i] && (best == -1 || uuTien(ds[i], ds[best]))) best = i;
        used[best] = true;
        cout << ds[best].ten << "\n";
    }
    return 0;
}

Sub 2: Sắp xếp — ~O(N log N)~

Sắp xếp toàn bộ danh sách bằng hàm so sánh (điểm giảm, tên tăng) rồi in T tên đầu. Đọc từng dòng và tách tên là phần trước token cuối, điểm là token cuối. Đạt 21/21 test.

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

struct NguoiHamMo {
    string ten;
    long long diem;
};

// Ưu tiên: điểm cao hơn trước; cùng điểm thì tên nhỏ hơn (từ điển) trước
bool uuTien(const NguoiHamMo &x, const NguoiHamMo &y) {
    if (x.diem != y.diem) return x.diem > y.diem;
    return x.ten < y.ten;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, T;
    cin >> N >> T;
    string line;
    getline(cin, line);  // bỏ phần còn lại của dòng đầu

    vector<NguoiHamMo> ds(N);
    for (int i = 0; i < N; i++) {
        getline(cin, line);
        while (!line.empty() && (line.back() == '\r' || line.back() == ' ')) line.pop_back();
        size_t p = line.find_last_of(' ');   // token cuối là điểm
        string ten = line.substr(0, p);
        while (!ten.empty() && ten.back() == ' ') ten.pop_back();
        ds[i].ten = ten;
        ds[i].diem = stoll(line.substr(p + 1));
    }

    // Sắp xếp theo thứ tự ưu tiên, rồi lấy T người đầu
    sort(ds.begin(), ds.end(), uuTien);
    for (int i = 0; i < T; i++) cout << ds[i].ten << "\n";
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.