Sắp xếp
Xem PDF
Điểm:
1900 (p)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Cho dãy số nguyên \(a_1,a_2,...,a_n\), ta sắp xếp lại dãy thành dãy không tăng bằng các bước như sau:
- Tìm số \(i\) nhỏ nhất thỏa mãn tồn tại số \(j\) sao cho \(i < j\) và \(a_i < a_j\).
- Nếu tồn tại số \(i\) như vậy, chuyển số \(a_i\) về cuối dãy.
- Nếu không tồn tại số \(i\) như vậy, kết thúc chương trình.
Yêu cầu: Cho dãy số nguyên ban đầu, hãy tính số bước cần thực hiện.
Input
- Dòng đầu gồm số nguyên \(n\) (\(1 \le n \le 3 \times 10^5\)).
- Dòng thứ hai chứa \(n\) số nguyên dương \(a_i\) (\(a_i \le 10^9\)).
Output
- Một số duy nhất là số bước cần thực hiện.
Scoring
- Subtask \(1\) (\(20\%\) số điểm): \(n \le 500\).
- Subtask \(2\) (\(20\%\) số điểm): \(n \le 5000\).
- Subtask \(3\) (\(20\%\) số điểm): \(a_i \le 3\).
- Subtask \(4\) (\(20\%\) số điểm): \(a_1 \le a_2 \le ... \le a_n\).
- Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.
Example
Test 1
Input
6
2 4 3 1 2 3Output
4Note
Các bước thực hiện như sau:
- \(4\) \(3\) \(1\) \(2\) \(3\) \(2\).
- \(4\) \(3\) \(2\) \(3\) \(2\) \(1\).
- \(4\) \(3\) \(3\) \(2\) \(1\) \(2\).
- \(4\) \(3\) \(3\) \(2\) \(2\) \(1\).
Bình luận
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
được rồi a nhé 😔
..