1 条题解

  • 0
    @ 2025-10-12 19:59:59

    题意: 给定由 01 组成的字符串,可通过任意次 “选择子串并循环左移任意正整数位” 的操作,让字符串最终满足非递减

    思路: 最终要让字符串有序,必须是​所有 0 排在左边,所有 1 排在右边​(像 “000...000111...111” 这样的形式)。

    如果原字符串里出现 “1 后面紧跟着 0” 的情况,就说明这两个字符的顺序 “乱了”(本该 0 在前、1 在后,现在反过来了)。每有 1 次这种 “乱序”,就至少需要 1 次操作去纠正。所以,“1 后跟 0” 的次数有多少,最少就需要多少次操作。

    #include <bits/stdc++.h>
    using namespace std;
    
    void solve() {
        char s[1000005];
        scanf("%s", s);
        int cnt = 0;
        int len = strlen(s);
        for(int i = 0; i < len; i++){
            if(s[i] == '1' && s[i + 1] == '0') {
                cnt++;
            }
        }
        cout << cnt << endl;
    }
    
    int main() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        solve();
        return 0;
    }
    
    • 1

    信息

    ID
    481
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    11
    已通过
    6
    上传者