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…
- 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++
- 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:
-
Nếu sự kiện là '+ i', tăng
countlê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.
- Kiểm tra nếu
-
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.
- Kiểm tra nếu
-
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.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.