← 返回题单
题单练习 字符串
← 上一题 下一题 →

A7049 | 换换删删

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给你一个只包含 0 和 1 的字符串 $s$。你可以对 $s$ 做两种操作：

  • 删除：删掉任意一个字符（代价 $1$）。
  • 交换：交换任意两位置的字符（代价 $0$，也就是免费）。
经过若干操作后得到一个新串 $t$。我们要求 $t$ 是好的：

把 $t$ 和原串 $s$ 左对齐，从左到右一位一位地比：

$t$ 的每一位都要和 $s$ 的同位置不同（0 对 1、1 对 0）。

如果 $t$ 比 $s$ 短，只比较 $s$ 的前 $|t|$ 位；空串也算合格。


你的任务是：最小化删除的次数，让得到的 $t$ 是好串，并输出这个最小删除次数。

输入格式

一行，一个二进制字符串 $s$（$1 \le |s| \le 2\times 10^5$；$s_i\in{0,1}$）。

输出格式

输出一个整数，表示使 $t$ 成为好串所需的最小删除代价。

输入输出样例

输入 #1
0
输出 #1
1
输入 #2
011
输出 #2
1
输入 #3
0101110001
输出 #3
0
输入 #4
111100
输出 #4
4
C++ 编辑器
输入
输出