P5362. 转盘配色

场次：2026年9月5日 · 来源：CodeFun2000 P5362

题目描述

装配线上有一只圆形转盘，沿圆周均布 $2m$ 个卡槽。每个卡槽里已经放好一块色片，黑色记为 0，白色记为 1，两种色片恰好各 $m$ 块。机械臂只能交换相邻两个卡槽里的色片；转盘是圆的，编号为 0 的卡槽与编号为 $2m-1$ 的卡槽也算相邻。

质检要求沿圆周看过去必须黑白严格交错，也就是任意两个相邻卡槽颜色都不同。色片只能靠相邻交换挪动，不能取出或替换。

请计算：最少交换多少次，才能让转盘变成严格交错。

约束：

• 1 $\le$ $m$ $\le$ 200000
• 色片串长度为 $2m$，只含 0 和 1，且两种字符各出现 $m$ 次

输入格式

第一行一个整数 $m$（1 $\le$ $m$ $\le$ 200000），表示每种颜色的块数。

第二行一个长度为 $2m$ 的字符串 $d$，只含字符 0 和 1，表示沿圆周依次写下的色片颜色。保证 0 与 1 的个数都是 $m$。

输出格式

输出一个整数，表示最少相邻交换次数。

示例

示例 1

输入：

2
1100

输出：

1

说明：

交换中间相邻的 1 与 0，得到 1010，已经黑白交错，操作 1 次。

示例 2

输入：

3
110100

输出：

1

说明：

首尾两个卡槽相邻。把位置 0 的 1 与位置 5 的 0 交换，得到 010101，操作 1 次。

示例 3

输入：

1
10

输出：

0

说明：

两个卡槽已经不同色，无需交换。