Queue Sort


Submit solution

Points: 2
Time limit: 1.0s
Memory limit: 977M

Author:
Problem type

Sau một buổi học Cấu trúc dữ liệu và giải thuật với thầy TICHPX, nqson vừa nghĩ ra một thuật toán Queue Sort có nội dung như sau:

Cho một dãy số gồm n số hạng khác nhau, ta cần tạo ra 2 hảng đợi để sắp xếp n số hạng đó. Hàng đợi đầu tiên (qu1) chứa tất cả các số trong dãy số từ trái sang phải, hàng đợi thứ hai (qu2) thì rỗng. Từng bước một, mỗi bước ta thực hiện một trong các trường hợp sau (ưu tiên từ trên xuống dưới):

  • Trường hợp 1: Nếu qu2 đang rỗng, ta lấy một tử đầu tiên của qu1 cho vào qu2
  • Trường hợp 2: Nếu phần tử đầu tiên của cả hai hàng đợi đều lớn hơn phần tử cuối cùng của qu1, ta lấy phần tử bé hơn trong hai hàng đợi đó ra khỏi hàng đợi rồi thêm nó vào cuối qu1
  • Trường hợp 3: Nếu phần tử đầu tiên của qu1 lớn hơn phần tử cuối cùng của cả hai hàng đợi, ta lấy phần tử đầu tiên của hàng đợi thứ nhất ra khỏi hàng đợi rồi thêm vào hàng đợi có phần tử cuối cùng lớn hơn
  • Trường hợp 4: Nếu một trong hai phần tử đầu tiên của hai hàng đợi lớn hơn phần tử cuối cùng của qu1, ta lấy phần tử lớn hơn trong hai hàng đợi đó ra khỏi hàng đợi rồi thêm nó vào cuối qu1
  • Trường hợp 5: Nếu phần tử đầu tiên của qu1 lớn hơn một trong hai phần tử cuối cùng của hai hàng đợi, ta lấy phần tử đầu tiên của hàng đợi thứ nhất ra khỏi hàng đợi rồi thêm vào hàng đợi có phần tử cuối cùng bé hơn
  • Trường hợp 6: Nếu tất cả các trường hợp trên không thỏa mãn, ta lấy phần tử ở đầu hàng đợi có giá trị bé hơn ra khỏi hàng đợi rồi thêm nó vào cuối qu1

Thực hiện đến khi qu1 không còn phần tử nào, qu2 sẽ chứa dãy số ban đầu được sắp xếp thành công.

In ra tổng số lượng các bước trên.

Giới hạn:

n100000

Đầu vào

Dòng đầu tiên là một số tự nhiên n

Dòng tiếp theo chứa n số trong dãy số đôi một khác nhau

Đầu ra

In ra tổng số lượng các bước để có thể sắp xếp thành công dãy số

Ví dụ 1:

Đầu vào

Copy
5
1 2 3 4 5

Đầu ra

Copy
5

Ví dụ 2:

Đầu vào

Copy
3
2 3 1

Đầu ra

Copy
7

Giải thích

Copy
Bắt đầu:
    qu1: 2 3 1
    qu2:
B1:
    qu1: 3 1
    qu2: 2
B2:
    qu1: 3 1 2
    qu2:
B3:
    qu1: 1 2
    qu2: 3
B4:
    qu1: 1 2 3
    qu2:
B5:
    qu1: 2 3
    qu2: 1
B6:
    qu1: 3
    qu2: 1 2
B7:
    qu1:
    qu2: 1 2 3

Comments

There are no comments at the moment.