1311 - BÃI ĐẬU XE HUTECH

Với bài này, dễ dàng nhận ra việc ta cần làm chính là tìm 2 vị trí mà khoảng cách lớn nhất và cho xe vào giữa và thêm 2 đoạn con sau khi thêm xe vào. Khi xe đi ra ta sẽ cập nhật 2 đoạn con thành 1.

Trong solution này, ta có thể sử dụng cấu trúc dữ liệu Set trong C++ để giải quyết vấn đề. Nếu bạn chưa biết về cấu trúc dữ liệu Set, hãy tìm hiểu tại đây.

Mã nguồn tham khảo:

#include <iostream>
#include <set>
#define MAX 1000009
#define ii pair <int, int>
#define iii pair <int, ii>
using namespace std;

set <iii> a;
int n, test;
int FL[MAX], FR[MAX], F[MAX];

iii mk_pair(int l, int r){
    if(l == 0 && r == n+1) return make_pair(-(999999999999), make_pair(1, n+1));
	if(l == 0) return make_pair(-(r-1), make_pair(1, r));
	if(r == n+1) return make_pair(-(n-l), make_pair(n, n+1));
	return make_pair(-(r - l) / 2, make_pair( (l + r) / 2, r));
}
int main(){
    cin>> n >> test;
    a.insert(mk_pair(0, n + 1));
    FL[n+1] = 0; FR[0] = n+1;
    while (test--){
        int t, id, l, r, m;
        cin >> t >> id;
        if (t == 1)
        {
            ii idn;
            idn = a.begin()->second;
            a.erase(a.begin());
            r = idn.second; 
            m = idn.first; 
            l = FL[r];
            F[id] = m;
            cout << m << endl;
            FL[m] = l; FR[m] = r;
            FL[r] = m; FR[l] = m;
            a.insert(mk_pair(l, m));
            a.insert(mk_pair(m, r));
        } 
        else
        {
            int m = F[id]; 
            l = FL[m], r = FR[m];
            FL[r] = l; FR[l] = r;
            a.erase(mk_pair(l,m));
            a.erase(mk_pair(m,r));
            a.insert(mk_pair(l,r));
        }
    }
}

Dưới đây là giải thích chi tiết về cách hoạt động của đoạn solution trên:

  • Đầu tiên, bạn định nghĩa một hàm mk_pair(l, r). Hàm này tạo ra một cặp <value, <position, right bound>>, nơi value là giá trị bạn muốn so sánh để sắp xếp các cặp. position là vị trí đỗ xe và right bound là ranh giới phải của khoảng trống.
  • Để tiện lợi cho việc so sánh, giá trị value được tính như sau:
    • Nếu l và r cùng bằng 0 và n+1 (khoảng trống ban đầu), value sẽ bằng -999999999999 để đảm bảo rằng nó luôn nhỏ nhất.
    • Nếu l bằng 0 (khoảng trống ở bên trái), value sẽ bằng -(r-1).
    • Nếu r bằng n+1 (khoảng trống ở bên phải), value sẽ bằng -(n-l).
    • Ngược lại, value sẽ bằng -(r - l) / 2. Điều này đảm bảo rằng khi có nhiều hơn một khoảng trống với cùng kích thước, khoảng trống có vị trí nhỏ hơn sẽ được chọn.
  • Trong hàm main, đoạn mã của bạn tiếp tục xử lý các xe đến và đi theo từng truy vấn. Khi một xe mới đến (t == 1), đoạn mã sẽ chọn một khoảng trống từ đầu của set (đại diện cho khoảng trống lớn nhất), cập nhật ranh giới của khoảng trống và chèn hai khoảng trống mới vào set. Khi một xe rời đi (t == 2), đoạn mã sẽ tìm và xóa hai khoảng trống tương ứng với vị trí xe rời đi, sau đó ghép nối hai khoảng trống đó thành một và chèn vào set.

Vì set trong C++ tự động sắp xếp các phần tử, việc tìm và chọn khoảng trống lớn nhất để đỗ xe mới trở nên đơn giản hơn. Tương tự, việc xóa và cập nhật thông tin vị trí khi một xe rời đi cũng được thực hiện một cách hiệu quả hơn.