[CF1204D2] Kirk and a Binary String

[CF1204D2] Kirk and a Binary String - 思维

Description

给定一个 01 串，要你求出另一个长度相等串使得任意区间内最长不降子序列的长度与原串相等且 0 的总数尽量多。

Solution

我们要将一些 1 改成 0，将某一个 1 改成 0 的条件是它后面的 0 的个数不少于 1 的个数，这个条件保证了这次修改不会影响正确性

在这个条件下，我们贪心地修改，倒序扫描整个序列，能修改就修改

括号序列视角：0 看成左括号，1 看成右括号，那么最长不降子序列就是最长的可以匹配的子括号序列长度，这样理解起来会很清楚

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6 + 5;

int n;
char s[N];

signed main()
{
    cin >> s + 1;
    n = strlen(s + 1);

    int stack_size = 0;
    for (int i = n; i >= 1; i--)
    {
        if (s[i] == '0')
        {
            ++stack_size;
        }
        else
        {
            if (stack_size > 0)
            {
                --stack_size;
            }
            else
            {
                s[i] = '0';
            }
        }
    }
    cout << s + 1 << endl;
}