CSES - Collecting Numbers | Thu thập số
Xem PDF
Điểm:
1300 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạn được cho một mảng mà chứa mỗi số giữa \(1\ldots n\) chính xác một lần. Nhiệm vụ của bạn là thu thập các số từ \(1\) đến \(n\) theo thứ tự tăng dần.
Trong mỗi vòng, bạn đi qua mảng từ trái sang phải và thu thập nhiều số nhất có thể. Tổng số lượng vòng sẽ là bao nhiêu?
Input
- Dòng đầu tiên có hai số nguyên \(n\): kích thước mảng.
- Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): các số trong mảng.
Output
- In một số nguyên: số lượng vòng.
Constraints
- \(1 \le n \le 2 \cdot 10^5\)
Example
Sample input
5
4 2 1 5 3
Sample output
3
Bình luận
Gợi ý
sắp xếp lại giá trị phần tử (nhớ lưu lại vị trí cũ của mỗi phần tử), sau đó xét xem vị trí cũ của phần tử nhỏ hơn có đứng sau vị trí cũ của phần tử lớn hơn nó không, nếu có thì ta phải chạy thêm 1 vòng để đến phần tử đó và do đó kết quả sẽ thêm 1
Code tại đây
https://ideone.com/ROFLhx
3 bình luận nữa