Codeforces Round #646 (Div. 2)【B. Subsequence Hate题解】

具体思路已经在代码注释中给出，这里不再赘述。

#include<iostream>

#include<algorithm>

using namespace std;

int t;

string s;

int main()

{

    cin >> t;

    while(t--)

    {

        cin >> s;

        int len = s.size();

        int total0 = 0, total1 = 0;

        for(int i = 0; i < len; i++)

        {

            total0 += (s[i] == '0');

            total1 += (s[i] == '1');

        }

        /**

            最终要把它变成111...000 或者 000...111 或者 全零 或者 全1

        */

        int ans = min(total0, total1);

        int nr0 = 0, nr1 = 0;

        for(int i = 0; i < len; i++)

        {

            nr0 += (s[i] == '0');

            nr1 += (s[i] == '1');

            /**

                假若把它变成111...000这种形式

                那么对于左部分是0的部分，要对它进行翻转(也就是对它进行操作),

                还要再加上右部分是1的个数

                这部分就是total1 - nr1,nr1此时扮演左半部分为1的个数，总的1的个数减去它，

                就是右半部分为1的个数。

            */

            ans = min(ans, nr0 + total1 - nr1);

            /**

            倘若把它变成000...111这种形式，思路和上面相似

            */

            ans = min(ans, nr1 + total0 - nr0);

        }

        cout << ans << endl;

    }

}

巴特西

Codeforces Round #646 (Div. 2)【B. Subsequence Hate题解】

最新文章

热门文章