Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIAi2 WildChat-4.8M (AI2)

Trên một chiếc xe Bus trống (chưa có khách) có � M ghế ngồi. Có tất cả � N hành khách…

  1. User

    Trên một chiếc xe Bus trống (chưa có khách) có � M ghế ngồi. Có tất cả � N hành khách được đánh số từ 1 1 đến � N, tất cả họ đều đang ở ngoài xe Bus. Có � Q sự kiện được ghi lại như sau:

    � i : mô tả người thứ � i tiến vào xe Bus; − − � i : mô tả người thứ � i ra khỏi xe Bus; Dữ liệu vào đảm bảo mỗi người chỉ ra hoặc vào nhiều nhất một lần.

    Hãy xác định chuỗi sự kiện đưa ra có hợp lý hay không (không hợp lý nếu có ai đó rời khỏi xe bus mà trước đó chưa từng lên xe bus, hoặc tại một thời điểm nào đó số lượng người trên xe bus nhiều hơn số ghế ngồi của xe). lập trình c++

  2. Assistant

    Để giải bài toán trên, ta có thể sử dụng một biến đếm count để đếm số lượng người trên xe Bus. Ban đầu, count được đặt bằng 0.

    Duyệt từng sự kiện trong chuỗi sự kiện đưa ra, ta thực hiện các bước sau:

    1. Nếu sự kiện là '+ i', tăng count lên 1.

      • Kiểm tra nếu count > M, tức là lượng người trên xe lớn hơn số ghế ngồi, in ra "NO" và kết thúc chương trình.
      • Nếu không, kiểm tra xem đã có người thứ i lên xe trước đó hay chưa. Nếu có, in ra "NO" và kết thúc chương trình.
    2. Nếu sự kiện là '- i', giảm count đi 1.

      • Kiểm tra nếu count < 0, tức là có người ra khỏi xe mà trước đó chưa từng lên xe, in ra "NO" và kết thúc chương trình.
    3. Nếu đã duyệt qua toàn bộ chuỗi sự kiện mà không có sự vi phạm nào, in ra "YES" để chỉ ra chuỗi sự kiện đưa ra là hợp lệ.

    Dưới đây là code C++ minh họa cho giải thuật trên:

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    int main() {
        int M, N, Q;
        cin >> M >> N >> Q;
    
        vector<bool> isOnBus(N + 1, false); // mảng lưu trạng thái của từng hành khách
    
        int count = 0; // biến đếm số lượng người trên xe
        bool isValid = true; // biến kiểm tra xem chuỗi sự kiện có hợp lệ hay không
    
        for (int i = 1; i <= Q; ++i) {
            char action;
            int person;
            cin >> action >> person;
    
            if (action == '+') { // hành động lên xe
                if (count >= M || isOnBus[person]) {
                    isValid = false;
                    break;
                }
                count++;
                isOnBus[person] = true;
            } else if (action == '-') { // hành động ra khỏi xe
                if (!isOnBus[person] || count <= 0) {
                    isValid = false;
                    break;
                }
                count--;
                isOnBus[person] = false;
            }
        }
    
        if (isValid && count == 0) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    
        return 0;
    }
    

    Độ phức tạp của giải thuật này là O(Q), với Q là số lượng sự kiện được ghi lại.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.