Xếp hàng chung
Đề bài
Mô tả
Hãy tưởng tượng bạn đang tổ chức một buổi biểu diễn ở trường. Bạn đã có học sinh của nhóm A đứng thành một hàng dọc, chiều cao của các em theo thứ tự là . Đúng lúc đó, một nhóm học sinh B gồm em với chiều cao muốn tham gia vào hàng.
Vấn đề là các học sinh nhóm A muốn giữ nguyên vị trí của mình (thứ tự giữa các em không đổi), nhưng các học sinh nhóm B rất linh hoạt và có thể đứng ở bất cứ đâu: ngay đầu hàng, giữa hai học sinh bất kỳ trong hàng, hoặc ở cuối hàng.
Một lỗi được tính khi một học sinh cao hơn đứng trước một học sinh thấp hơn, tức là mỗi cặp vị trí trong hàng cuối cùng mà học sinh ở vị trí cao hơn hẳn học sinh ở vị trí tính là một lỗi. Sau khi xếp các học sinh nhóm B vào hàng của nhóm A, số lỗi nhỏ nhất có thể là bao nhiêu?
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Dòng đầu tiên chứa số nguyên () là số bộ test. Mỗi bộ test gồm:
- Dòng thứ nhất chứa hai số nguyên và () là số học sinh của nhóm A và nhóm B.
- Dòng thứ hai chứa số nguyên () là chiều cao các học sinh nhóm A.
- Dòng thứ ba chứa số nguyên () là chiều cao các học sinh nhóm B.
Dữ liệu đảm bảo tổng của tất cả các bộ test không vượt quá và tổng của tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in ra một số nguyên là số lỗi nhỏ nhất có thể.
Ràng buộc
- Tổng không vượt quá , tổng không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 3 3 2 1 1 2 3 3 4 1 2 3 4 3 2 1 5 4 1 3 5 3 1 4 3 6 1 |
4 0 6 |
Bộ test thứ nhất: chẳng hạn hàng có lỗi. Bộ test thứ hai: hàng không có lỗi nào. Bộ test thứ ba: chẳng hạn hàng có lỗi. |
| 1 3 3 2 2 2 3 1 2 |
0 | Xếp thành : hai học sinh cao bằng nhau đứng cạnh nhau không tính là lỗi. |
Bình luận