| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P165PROB - ROUND 5B - Trồng cây |
Tại Học viện Hoàng gia PTIT, có 1 clb mới nổi và thu hút rất nhiếu sự quan tâm của các bạn trẻ. Đó chính là CLB Cây cối. Thu là 1 người năng nổ, cô tham gia ở mọi CLB mà cô cảm thấy thích thú, và CLB Cây cối không phải ngoại lệ. Ngay khi nghe tin CLB tuyển thành viên, Thu đã lập tức nộp đơn đăng ký.
Thu đã xuất sắc vượt qua vòng phỏng vấn để đến vòng test IQ, nếu Thu vượt qua bài test này, cô ấy sẽ trở thành thành viên chính thức của CLB Cây cối. Hãy giúp Thu hoàn thành bài test này nhé:
Cho n cây thuộc m loài cây khác nhau, xếp trên 1 đường thẳng. Cây thứ i sẽ có thông số t[i] và x[i] trong đó t[i] là loài cây (1 <= t[i] <= m), x[i] là tọa độ kiểu số thực của cây tương ứng trên trục tọa độ. Hãy di chuyển các cây sao cho các cây cùng loài luôn đứng cạnh nhau, và từ trái sang phải trên trục tọa độ, chỉ số của loài cây sẽ tăng dần từ 1 đến m. Biết mỗi lần di chuyển là lấy 1 cây và đặt nó vào 1 vị trí bất kì trên trục tọa độ. Hãy xác định số lần di chuyển ít nhất để thỏa mãn yêu cầu trên.
Input
Dòng đầu tiên nhập 2 số tự nhiên n và m (1 <= m <= n <= 5000). Trong đó n là số cây, m là số loài cây.
n dòng tiếp theo, mỗi dòng nhậpsố tự nhiên t[i] và số thực x[i] (1 <= t[i] <= m, 0 <= x[i] <= 109). Trong đó t[i] là chỉ số của loài cây thứ i, x[i] là tọa độ cây thứ i.
Output
In ra số lần di chuyển cây nhỏ nhất.
Example
Test 1:
Input:
1 1
1 0
Output:
0
Test 2:
Input:
3 3
1 5.0
2 5.5
3 6.0
Output:
0
Test 3:
Input:
5 5
5 0.2
4 1.2
3 2.2
2 3.2
1 4.2
Output:
4
| Được gửi lên bởi: | adm |
| Ngày: | 2016-03-25 |
| Thời gian chạy: | 1s-2s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
