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

View as PDF



Author:
Problem types
Points: 1700 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

Here are some possible methods using which we can sort the elements of an array in increasing order:

  1. At each step, choose two adjacent elements and swap them.
  2. At each step, choose any two elements and swap them.
  3. At each step, choose any element and move it to another position.
  4. At each step, choose any element and move it to the front of the array.

Given a permutation of numbers \(1,2,…,n\), calculate the minimum number of steps to sort the array using the above methods.

Input

  • The first input line contains an integer \(n\).
  • The second line contains \(n\) integers describing the permutation.

Output

  • Print four numbers: the minimum number of steps using each method.

Constraints

  • \(1\leq n \leq 2 ⋅ 10^5\)

Example

Sample input

8  
7 8 2 6 5 1 3 4

Sample output

20 6 5 6

Comments


  • 1
    Thanh72    10:52 p.m. 18 aug, 2023 edited

    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