← 返回题目
题库练习 换换删删
← 上一题 下一题 →

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++ 编辑器
输入
输出