D. 第4题-01串的代价

第4题-01串的代价

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

小美是一个喜欢研究密码的人,他经常在网上寻找各种有趣的密码挑战。他最近发现了一个神秘的网站,网站上只有一个输入框和一个提交按钮,没有任何提示。小美好奇地输入了一些内容,发现网站会返回一个长度为 nn0101 串,只包含字符 01 的串。小美觉得这个串一定是一个密码的线索,他想要破解它。

小美仔细观察了这个串,发现它里面隐藏着一些规律,比如有些位置的字符总是相同的,有些位置的字符总是相反的。小美猜测这些规律可能是密码的组成部分,他想要把它们都保留下来,并且删除掉无关的字符。但是,小美不想删除太多的字符,也不想保留太长的串。所以,他想知道,在保证删除一个前缀和一个后缀的情况下(前缀和后缀都可以为空),即保留一个原串的连续子串(可以为空),他需要最小化以下代价:

  1. 被删除的字符 1 的个数;
  2. 剩下的子串的字符 0 的个数。

小美会给你总共若干次询问,每次询问他会告诉你网站返回给他的 0101 串。你需要帮助小美判断,在每次询问中,他需要输出的最小代价是多少。

输入描述

一个长度为 n(1n1e5)n(1 \leq n \leq 1e5)0101 字符串。

输出描述

一个整数,表示最小的操作代价。

样例1

输入

101110110

输出

样例解释

删除前两个字符和最后一个字符,代价为 11

保留下来的字符中有一个 00 ,代价为 11 ,故代价之和为 22

样例2

输入

1010110001

输出

春招模拟赛第十六场|美团|2023.4.23

Not Attended
Status
Done
Rule
IOI
Problem
4
Start at
2023-5-5 19:00
End at
2023-5-5 21:00
Duration
2 hour(s)
Host
Partic.
53