非递减字符串

GitHub跳转原题关系图返回列表

非递减的最终串只能是 A…AB…B 的形态，枚举分割点并用前缀和 O(1) 计算翻转代价。

OJ: roj

题目 ID: 20026

难度:普及-

标签:字符串枚举前缀和

创建: 2026-09-06 15:54

更新: 2026-10-07 13:50

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

给定一个长度为 nn 的、仅由字符 A 和 B 组成的字符串 SS。每次操作可以把任意一个字符翻成另一个。求最少多少次操作后，字符串变成非递减的（即最终串形如 ApBn−pA^p B^{n-p}）。

输入为一行字符串 SS；输出一个整数表示最少操作次数。1≤n≤1061\le n\le 10^6。

样例输入：AABBA，样例输出：1。

思路

最终合法串只能是前 pp 个 A 接后 n−pn-p 个 B，共 n+1n+1 种形态。枚举分割点 pp，代价为前 pp 位中 B 的个数加上后 n−pn-p 位中 A 的个数，用前缀和 O(1)O(1) 计算，取最小值。

参考代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-06 15:54
 * update_at: 2026-10-06 09:13
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int n;
char s[MAXN];
int preA[MAXN]; // preA[i] 表示前 i 位中 A 的个数
int preB[MAXN]; // preB[i] 表示前 i 位中 B 的个数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> (s + 1);
    n = strlen(s + 1);

    // 前缀计数：preA[i]、preB[i]
    for (int i = 1; i <= n; i++) {
        preA[i] = preA[i - 1] + (s[i] == 'A');
        preB[i] = preB[i - 1] + (s[i] == 'B');
    }

    // 枚举最终形态：前 p 位全 A，后 n-p 位全 B
    int ans = n;
    for (int p = 0; p <= n; p++) {
        // 前 p 位里的 B 要翻成 A；后 n-p 位里的 A 要翻成 B
        int cost = preB[p] + (preA[n] - preA[p]);
        ans = min(ans, cost);
    }

    cout << ans << "\n";
    return 0;
}