测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A7049. 换换删删

编程题 普及-
知识点

题目描述

给你一个只包含 01 的字符串 $s$。你可以对 $s$ 做两种操作:

- **删除**:删掉任意一个字符(代价 $1$)。
- **交换**:交换任意两位置的字符(代价 $0$,也就是免费)。

经过若干操作后得到一个新串 $t$。我们要求 $t$ 是**好**的:

> 把 $t$ 和原串 $s$ **左对齐**,从左到右一位一位地比:
> **$t$ 的每一位都要和 $s$ 的同位置不同**(0110)。
> 如果 $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

说明/提示

$1 \le |s| \le 2\times 10^5$。
上一题 去做题 下一题