Phân tích bài toán Trò chơi Hoàng hậu

Giới thiệu bài toán

Bài toán Trò chơi Hoàng hậu là một biến thể của bài toán Trò chơi Vua từ kỳ thi NOIP 2012. Yêu cầu của bài toán là sắp xếp lại thứ tự các quan đại thần sao cho số tiền thưởng lớn nhất mà một vị đại thần nhận được được giảm thiểu đến mức có thể.

Quy tắc tính thưởng

Giả sử số ở tay trái của vị đại thần thứ \\(i\\) là \\(a\_i\\), số ở tay phải là \\(b\_i\\), khi đó:

• Thưởng của đại thần thứ nhất: \\(c\_1 = a\_1 + b\_1\\)
• Thưởng của đại thần thứ \\(i\\) (với \\(i \\geq 2\\)): \\(c\_i = \\max(c\_{i-1}, \\sum\_{j=1}^{i} a\_j) + b\_i\\)

Phương pháp giải quyết

Quan sát quan trọng

Tương tự như bài toán Trò chơi Vua, chúng ta cần tìm ra một thứ tự sắp xếp các đại thần hợp lý. Phân tích cho thấy thứ tự sắp xếp sẽ ảnh hưởng đến giá trị thưởng tối đa cuối cùng.

Chiến lược sắp xếp

Hàm so sánh trong mã nguồn là yếu tố cốt lõi:

bool soSanh(nut a, nut b) {
    if(a.giaTriTrai <= a.giaTriPhai && a.giaTriTrai <= b.giaTriTrai || b.giaTriTrai <= a.giaTriTrai && b.giaTriTrai <= b.giaTriPhai) 
        return a.giaTriTrai != b.giaTriTrai ? a.giaTriTrai < b.giaTriTrai : a.giaTriPhai > b.giaTriPhai;
    return a.giaTriPhai != b.giaTriPhai ? a.giaTriPhai > b.giaTriPhai : a.giaTriTrai < b.giaTriTrai;
}

Ý nghĩa của hàm so sánh này:

1. Nếu đại thần A thỏa mãn \\(a\_x \\leq a\_y\\) và \\(a\_x \\leq b\_x\\), hoặc đại thần B thỏa mãn \\(b\_x \\leq a\_x\\) và \\(b\_x \\leq b\_y\\), thì:
   • Ưu tiên sắp xếp theo \\(x\\) tăng dần
   • Nếu \\(x\\) bằng nhau, sắp xếp theo \\(y\\) giảm dần
2. Nếu không, thì:
   • Ưu tiên sắp xếp theo \\(y\\) giảm dần
   • Nếu \\(y\\) bằng nhau, sắp xếp theo \\(x\\) tăng dần

Thuật toán

1. Đọc dữ liệu đầu vào
2. Sắp xếp các đại thần theo quy tắc đã nêu ở trên
3. Tính toán dãy thưởng sau khi sắp xếp:
   • Duy trì tổng tiền mặt \\(tongTienMat\\) của các đại thần đã xử lý
   • Duy trì giá trị tối đa \\(giaTriLonNhat\\)
   • Đối với mỗi đại thần, cập nhật tổng tiền mặt và tính thưởng của họ

Cài đặt mã nguồn

#include<iostream>
#include<algorithm>
using namespace std;

int soTest = 1, soNhanVat;
long long tongTienMat, giaTriLonNhat;

struct nut {
    int giaTriTrai, giaTriPhai, id;
} dsNhanVat[20005];

bool soSanh(nut a, nut b) {
    if(a.giaTriTrai <= a.giaTriPhai && a.giaTriTrai <= b.giaTriTrai || b.giaTriTrai <= a.giaTriTrai && b.giaTriTrai <= b.giaTriPhai) 
        return a.giaTraiTrai != b.giaTriTrai ? a.giaTriTrai < b.giaTriTrai : a.giaTriPhai > b.giaTriPhai;
    return a.giaTriPhai != b.giaTriPhai ? a.giaTriPhai > b.giaTriPhai : a.giaTriTrai < b.giaTriTrai;
}

int main() {
    cin >> soTest;
    while(soTest--) {
        tongTienMat = 0; giaTriLonNhat = 0;
        cin >> soNhanVat;
        for(int i = 1; i <= soNhanVat; i++) {
            cin >> dsNhanVat[i].giaTriTrai >> dsNhanVat[i].giaTriPhai;
            dsNhanVat[i].id = i;
        }
        
        sort(dsNhanVat + 1, dsNhanVat + soNhanVat + 1, soSanh);
        
        for(int i = 1; i <= soNhanVat; i++) {
            tongTienMat += dsNhanVat[i].giaTriTrai;
            if(giaTriLonNhat < tongTienMat) 
                giaTriLonNhat = tongTienMat + dsNhanVat[i].giaTriPhai;
            else 
                giaTriLonNhat += dsNhanVat[i].giaTriPhai;
        }
        
        cout << giaTriLonNhat << endl;
        for(int i = 1; i <= soNhanVat; i++) 
            cout << dsNhanVat[i].id << " ";
    }
    return 0;
}

Phân tích ví dụ

Ví dụ 1

Đầu vào:

1
3
4 1
2 2
1 2

Thứ tự các đại thần sau khi sắp xếp: 3(1,2), 2(2,2), 1(4,1)

Quá trình tính toán:

• Đại thần 3: thưởng = 1 + 2 = 3
• Đại thần 2: thưởng = max(3, 1+2) + 2 = max(3,3) + 2 = 5
• Đại thần 1: thưởng = max(5, 1+2+4) + 1 = max(5,7) + 1 = 8

Đầu ra: 8

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

• Độ phức tạp thời gian: \\(O(T \\cdot n \\log n)\\), chủ yếu đến từ thao tác sắp xếp
• Độ phức tạp không gian: \\(O(n)\\), dùng để lưu thông tin các đại thần

Kết luận

Điểm mấu chốt của bài toán này là tìm ra thứ tự sắp xếp các đại thần phù hợp. Thông qua quy tắc sắp xếp đặc biệt, chúng ta có thể giảm thiểu giá trị thưởng tối đa. Chiến lược tham lam này xem xét mối quan hệ giữa các giá trị tay trái và tay phải của các đại thần, ưu tiên xử lý những đại thần có "giá trị tay trái nhỏ" hoặc "giá trị tay phải lớn", từ đó cân bằng việc phân bổ thưởng.

Loại bài toán sử dụng chiến lược tham lam như vậy đòi hỏi phải phân tích kỹ đặc điểm bài toán, tìm ra quy tắc so sánh phù hợp, là một dạng bài kinh điển trong các kỳ thi lập trình thuật toán.