徐老师的羊腿修整
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师最近从国外订购了一个超极品羊腿！
这个羊腿超级大，质量超级好，但是非常可惜，因为运送路途遥远，它中间有一部分的肉看起来不再那么优秀
于是徐老师决定修整一下这只羊腿
但是徐老师并不会专业师傅的 `薄切刀法`，只会他独创的 `迪拜刀法`，也就是直接挑两个位置，咔嚓两刀，去头去尾，保留中间部分！(当然徐老师可以选择不切，或者扔掉整个羊腿)
假设这只羊腿现在被徐老师看作是从左往右依次 $n$ 个均匀的部分，每个部分的羊腿肉可以用一个符号 $A$ 来表示非常极品，用一个符号 $B$ 来表示不再那么优秀
显然对于徐老师来说，他切掉的 $A$ 越多，留下的 $B$ 越多，就会越心痛
但是老生常谈的一句话——鱼和熊掌不可兼得
在切的同时一定会同时切掉 $A$ 和 $B$ 类的肉
所以徐老师最后决定，不同切法的心痛程度=$max($切掉$A$的数量，留下$B$的数量$)$
现在徐老师想知道对于这只羊腿，他的心痛程度最小是多少？
输入格式
输入第一行包含一个整数 $n$ 表示羊腿长度
接下来一行一个长度为 $n$ 仅由 $A,B$ 组成的字符串，表示这个羊腿从左往右每个部分肉的品质
| 数据点编号 | $n$的范围 |
| ---------- | ---------------------- |
| $1$ | $1 \leq n \leq 100$ 且字符串只包含$A$ |
| $2$~$3$ | $1 \leq n \leq 10^2$ |
| $4$~$5$ | $1 \leq n \leq 2*10^3$ |
| $6$~$10$ | $1 \leq n \leq 2*10^6$ |
输出格式
输出徐老师最小的心痛程度
样例
13
ABBABBABBABBA32023暑CSP-S复赛集训模拟赛五
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-8-1 22:15
- 结束于
- 2023-8-11 22:15
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 16
