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.
小美是一个喜欢研究密码的人,他经常在网上寻找各种有趣的密码挑战。他最近发现了一个神秘的网站,网站上只有一个输入框和一个提交按钮,没有任何提示。小美好奇地输入了一些内容,发现网站会返回一个长度为 n 的 01 串,只包含字符 0
和 1
的串。小美觉得这个串一定是一个密码的线索,他想要破解它。
小美仔细观察了这个串,发现它里面隐藏着一些规律,比如有些位置的字符总是相同的,有些位置的字符总是相反的。小美猜测这些规律可能是密码的组成部分,他想要把它们都保留下来,并且删除掉无关的字符。但是,小美不想删除太多的字符,也不想保留太长的串。所以,他想知道,在保证删除一个前缀和一个后缀的情况下(前缀和后缀都可以为空),即保留一个原串的连续子串(可以为空),他需要最小化以下代价:
1
的个数;0
的个数。小美会给你总共若干次询问,每次询问他会告诉你网站返回给他的 01 串。你需要帮助小美判断,在每次询问中,他需要输出的最小代价是多少。
一个长度为 n(1≤n≤1e5) 的 01 字符串。
一个整数,表示最小的操作代价。
输入
101110110
输出
2
样例解释
删除前两个字符和最后一个字符,代价为 1 ;
保留下来的字符中有一个 0 ,代价为 1 ,故代价之和为 2 。
输入
1010110001
输出
3