Hiệu Ứng Nhà Kính

Điểm: 5,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Emuskald có một nhà kính dài vô tận, trồng $n$ cây thuộc $m$ loài khác nhau, đánh số từ $1$ đến $m$ . Nhà kính được xem như một đường thẳng vô hạn, mỗi cây nằm tại một điểm.

Anh muốn đặt $m - 1$ vách ngăn để chia nhà kính thành $m$ phần liên tiếp (đánh số $1, 2, \dots, m$ từ trái sang phải) sao cho tất cả cây thuộc loài $i$ đều nằm trong phần thứ $i$ . Các vách có thể đặt tại vị trí thực bất kỳ.

Vì không phải lúc nào cũng đặt được, Emuskald được phép đào lên một số cây và trồng lại tại vị trí thực bất kỳ (miễn vị trí đó chưa có cây). Hãy tìm số cây ít nhất cần phải trồng lại.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .
$n$ dòng tiếp theo, mỗi dòng gồm một số nguyên $s_{i}$ và một số thực $x_{i}$ — loài và vị trí của cây thứ $i$ . Mỗi $x_{i}$ có không quá $6$ chữ số thập phân.

Các giá trị $x_{i}$ đôi một khác nhau, mỗi loài xuất hiện ít nhất một lần, và các cây được liệt kê theo thứ tự tăng dần của $x_{i}$ .

Dữ liệu ra

In ra một số nguyên duy nhất — số cây ít nhất phải trồng lại.

Ràng buộc

$1 \leq n, m \leq 5000$ , $n \geq m$ .
$1 \leq s_{i} \leq m$ .
$0 \leq x_{i} \leq 10^{9}$ .

Ví dụ

Input	Output	Giải thích
3 2 2 1 1 2.0 1 3.100	1	Trồng lại cây loài 2 sang bên phải hai cây loài 1.
3 3 1 5.0 2 5.5 3 6.0	0	Các loài đã ở đúng thứ tự, không cần trồng lại.
6 3 1 14.284235 2 17.921382 1 20.328172 3 20.842331 1 25.790145 1 27.204125	2	Giữ lại dãy loài $1, 1, 1, 1$ (bốn cây loài 1 theo thứ tự); hai cây loài $2$ và $3$ phải trồng lại.

Bình luận

Không có bình luận tại thời điểm này.