Phân Chia Khu Vực
Đề bài
Mô tả
Farmer John có con bò xếp thành một hàng, mỗi con thuộc giống Holstein (ký hiệu 'H') hoặc Guernsey (ký hiệu 'G'). Ông muốn chia hàng bò thành các nhóm liên tiếp, mỗi con bò thuộc đúng một nhóm và mỗi nhóm có tối đa con bò. Một nhóm được gọi là không thuận lợi nếu số bò Guernsey trong nhóm đó lớn hơn hoặc bằng số bò Holstein.
Hãy tìm cách chia sao cho số nhóm không thuận lợi là ít nhất có thể.
Dữ liệu vào
- Dòng đầu: hai số nguyên và ()
- Dòng thứ hai: xâu ký tự độ dài gồm các ký tự 'H' và 'G'
Dữ liệu ra
Một số nguyên duy nhất: số nhóm không thuận lợi ít nhất.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 2 HGHGGHG |
3 | Một cách chia tối ưu: [H][G][H][GG][H][G]. Các nhóm [G], [GG], [G] là không thuận lợi (số bò G ≥ số bò H), còn ba nhóm [H] thì thuận lợi. Tổng cộng 3 nhóm không thuận lợi. |
| 6 3 GHHGGH |
1 | Chia thành [GHH][GGH]: nhóm đầu có 2 bò H và 1 bò G nên thuận lợi, nhóm sau có 2 bò G và 1 bò H nên không thuận lợi. Không thể đạt 0 vì cả hàng có 3 bò G và 3 bò H, nên luôn tồn tại ít nhất một nhóm có số bò G không ít hơn số bò H. |
Bình luận