Hướng dẫn giải của [200 đề thầy Đức] Bài 3: Lịch khám bệnh
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.
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
Có N bệnh nhân, cứ sau X phút lại có một bệnh nhân mới đến, bác sĩ khám mỗi người mất 10 phút. Cần tìm thời gian người cuối cùng phải chờ.
Cách làm
Ta mô phỏng lại quá trình khám bệnh theo từng người, theo thứ tự đến:
- Bệnh nhân thứ i (đánh số từ 0) đến lúc i*X phút.
- Bác sĩ chỉ rảnh sau khi khám xong người trước. Nếu bác sĩ đang bận thì bệnh nhân phải chờ, nên bắt đầu khám lúc max(lúc đến, lúc bác sĩ rảnh).
- Thời gian chờ của bệnh nhân = lúc bắt đầu khám - lúc đến. Sau đó bác sĩ rảnh lúc bắt đầu + 10.
Sau khi xử lý hết N bệnh nhân, thời gian chờ được ghi nhận ở bệnh nhân cuối cùng chính là đáp số. Nhớ dùng long long cho thời gian.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, x;
cin >> n >> x;
// finish: thời điểm bác sĩ rảnh (sau khi khám xong bệnh nhân trước)
long long finish = 0;
long long wait = 0;
for (int i = 0; i < n; i++) {
// Bệnh nhân thứ i+1 đến phòng khám lúc i*x phút
long long arrive = (long long)i * x;
// Bắt đầu khám khi bác sĩ rảnh, nếu bác sĩ còn bận thì phải chờ
long long start = max(arrive, finish);
wait = start - arrive;
// Bác sĩ khám mất 10 phút cho mỗi bệnh nhân
finish = start + 10;
}
cout << wait << "\n";
}
return 0;
}
Bình luận