Sắp xếp (THTC Vòng KVMB 2022)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small, _minhduc
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1600 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên \(a_1, a_2, \dots, a_n\), ta sắp xếp lại dãy thành dãy không tăng bằng các bước như sau:

  • Tìm số \(i\) nhỏ nhất thỏa mãn tồn tại số \(j\) sao cho \(i < j\) và \(a_i < a_j\).
  • Nếu tồn tại số \(i\) như vậy, chuyển số \(a_i\) về cuối dãy.
  • Nếu không tồn tại số \(i\) như vậy, kết thúc chương trình.

Yêu cầu

Cho dãy số nguyên ban đầu, hãy tính số bước cần thực hiện.

Input

  • Dòng đầu gồm số nguyên \(n\) (\(1 \le n \le 3 \cdot 10^5\)).
  • Dòng thứ hai chứa \(n\) số nguyên dương \(a_i\) (\(a_i \le 10^9\)).

Output

  • Ghi ra thiết bị ra chuẩn một số duy nhất là số bước cần thực hiện.

Example

Test 1

Input 
6
2 4 3 1 2 3
Output 
4
Note

Các bước thực hiện như sau:

  • Bước 1: \(i=1\) (do \(a_1=2 < a_2=4\)), chuyển \(a_1\) về cuối: 4 3 1 2 3 2
  • Bước 2: \(i=3\) (do \(a_3=1 < a_4=2\)), chuyển \(a_3\) về cuối: 4 3 2 3 2 1
  • Bước 3: \(i=3\) (do \(a_3=2 < a_4=3\)), chuyển \(a_3\) về cuối: 4 3 3 2 1 2
  • Bước 4: \(i=5\) (do \(a_5=1 < a_6=2\)), chuyển \(a_5\) về cuối: 4 3 3 2 2 1
  • Kết thúc: Dãy đã là dãy không tăng.

Scoring

  • Có \(20\%\) số test ứng với \(20\%\) số điểm có \(n \le 500\).
  • Có \(20\%\) số test khác ứng với \(20\%\) số điểm có \(n \le 5000\).
  • Có \(20\%\) số test khác ứng với \(20\%\) số điểm có \(a_i \le 3\).
  • Có \(20\%\) số test khác ứng với \(20\%\) số điểm có \(a_1 \le a_2 \le \dots \le a_n\).
  • Có \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

Bình luận (4)

Mới nhất
Tải bình luận...

Kỳ thi: