CSES - Sorting Methods | Các phương pháp sắp xếp
Xem PDF
Điểm:
1700 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Dưới đây là một số phương pháp có thể sử dụng mà chúng ta có thể sắp xếp các phần tử của một mảng theo thứ tự tăng dần:
- Ở mỗi bước, chọn hai phần tử liền kề và hoán đổi chúng.
- Ở mỗi bước, chọn hai phần tử bất kỳ và hoán đổi chúng.
- Tại mỗi bước, chọn bất kỳ phần tử nào và di chuyển nó đến vị trí khác.
- Ở mỗi bước, chọn bất kỳ phần tử nào và di chuyển phần tử đó lên phía trước của mảng.
Cho một hoán vị của các số \(1,2,…, n\), hãy tính số bước tối thiểu để sắp xếp mảng bằng các phương pháp trên.
Input
- Dòng đầu tiên chứa một số nguyên \(n\).
- Dòng thứ hai chứa \(n\) số nguyên mô tả hoán vị.
Output
- In ra bốn số: số bước tối thiểu sử dụng mỗi phương pháp, mỗi số cách nhau bởi dấu cách.
Constraints
- \(1 \le n \le 2 \times 10^5\).
Example
Sample input
8
7 8 2 6 5 1 3 4
Sample output
20 6 5 6
Bình luận
Dưới đây là một số phương pháp có thể sử dụng mà chúng ta có thể sắp xếp các phần tử của một mảng theo thứ tự tăng dần:
Cho một hoán vị của các số \(1,2,…,n\), hãy tính số bước tối thiểu để sắp xếp mảng bằng các phương pháp trên.
Input
Output
Test 1
Input
Output