Xử Lý Lệnh Rút Tiền VietinBank

Mô tả

Phòng giao dịch VietinBank nhận rất nhiều lệnh rút tiền online từ ứng dụng di động. Mỗi lệnh gửi đến sẽ được nhân viên quầy đưa vào một danh sách chờ. Để ưu tiên khách hàng có giao dịch giá trị cao, nhân viên áp dụng quy tắc: cứ mỗi giây trôi qua, họ sẽ chọn ra lệnh có số tiền rút lớn nhất đang chờ để xử lý trước. Nếu có nhiều lệnh cùng số tiền, ai gửi đến trước sẽ được phục vụ trước.

Hệ thống ghi lại danh sách tất cả các lệnh theo thứ tự thời gian gửi đến. Bạn hãy cho biết: nếu nhân viên xử lý chính xác một lệnh mỗi giây, thì thứ tự các lệnh được xử lý sẽ ra sao?

Đầu vào

• Dòng đầu chứa số nguyên dương n — số lượng lệnh rút tiền.
• Dòng thứ hai chứa n số nguyên dương a[1], a[2], ..., a[n], trong đó a[i] là số tiền của lệnh thứ i. Thứ tự trong mảng chính là thứ tự thời gian gửi đến.

Đầu ra

• In ra một dòng chứa n số nguyên, là số tiền của các lệnh theo thứ tự được xử lý (từ giây thứ nhất đến giây thứ n), các số cách nhau bởi một khoảng trắng.

Ràng buộc

• 1 <= n <= 1000
• 1 <= a[i] <= 10^6

Ví dụ

Đầu vào:

5 300000 1500000 500000 1500000 800000

Đầu ra:

1500000 1500000 800000 500000 300000

Giải thích từng bước:

• Giây 1: Danh sách chờ có [300000]. Lệnh lớn nhất là 300000 → xử lý ngay. Nhưng khoan, hệ thống đã nhận đủ cả 5 lệnh trước khi bắt đầu xử lý!

Cách hiểu đúng: toàn bộ n lệnh đã nằm sẵn trong hàng đợi, và mỗi giây ta chọn ra phần tử lớn nhất. Khi có hai phần tử cùng giá trị, phần tử xuất hiện trước trong mảng gốc được chọn trước.

• Giây 1: Chọn 1500000 (lệnh thứ 2, xuất hiện trước lệnh thứ 4).
• Giây 2: Chọn 1500000 (lệnh thứ 4).
• Giây 3: Chọn 800000 (lệnh thứ 5).
• Giây 4: Chọn 500000 (lệnh thứ 3).
• Giây 5: Chọn 300000 (lệnh thứ 1).