Chụp Ảnh

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John muốn sắp xếp $N$ con bò ( $2 \leq N \leq 2 \times 10^{5}$ , $N$ chẵn) đứng thành hàng sao cho số bò Guernsey chiếm vị trí chẵn là nhiều nhất có thể. Mỗi con bò hoặc là Guernsey (G) hoặc Holstein (H).

Phép toán duy nhất mà Farmer John có thể thực hiện là đảo ngược một tiền tố có độ dài chẵn. Hãy tìm số lần đảo ngược tối thiểu cần thực hiện để đạt được cách sắp xếp tối ưu.

Dữ liệu vào

Dòng 1: Số nguyên $N$
Dòng 2: Xâu ký tự độ dài $N$ gồm các ký tự 'G' và 'H'

Dữ liệu ra

Một số nguyên duy nhất — số lần đảo ngược tiền tố tối thiểu cần thực hiện.

Ràng buộc

$2 \leq N \leq 2 \times 10^{5}$ , $N$ chẵn
Test 2-6: $N \leq 1000$
Test 7-11: Không có ràng buộc thêm

Ví dụ

Input	Output	Giải thích
14 GGGHGHHGHHHGHG	1	Đảo ngược 6 con bò đầu tiên biến "GGGHGH..." thành "HGHGGG...", tăng số Guernsey ở vị trí chẵn từ 4 lên 6 (tối ưu).

Bình luận

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