CSES - Sorting Methods | Các phương pháp sắp xếp

Xem PDF



Tác giả:
Dạng bài
Đ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:

  1. Ở mỗi bước, chọn hai phần tử liền kề và hoán đổi chúng.
  2. Ở mỗi bước, chọn hai phần tử bất kỳ và hoán đổi chúng.
  3. 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.
  4. Ở 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


  • 0
    Thanh72 10:52 p.m. 18 Tháng 8, 2023 đã chỉnh sửa

    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:

    1. Ở mỗi bước, chọn hai phần tử liền kề và hoán đổi chúng.
    2. Ở mỗi bước, chọn hai phần tử bất kỳ và hoán đổi chúng.
    3. 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.
    4. Ở 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(1 \leq n \leq 2 \times 10^5)\).
    • Dòng thứ hai chứa \(n\) số nguyên mô tả hoán vị.

    Output

    • Gồm một dòng chứa \(4\) số: số bước tối thiểu để sắp xếp lại mảng theo thứ tự tăng dần sử dụng mỗi phương pháp.

    Test 1

    Input
    8  
    7 8 2 6 5 1 3 4
    Output
    20 6 5 6