ARC157 B 题解

原题链接：https://atcoder.jp/contests/arc157/tasks/arc157_b。

首先我们简化问题。

用 $cnt_X$ 表示字符串中字符 X 的个数，
如果 $k \le cnt_X$，那么我们显然要从字符串中找到 $k$ 个 X，并将它们变为 Y；
如果 $k > cnt_X$，那么我们可以将问题变为：将字符串中每一位反转，再从新字符串中选取 $n - k$ 个 X 变为 Y。

然后再来解决问题。

下文相邻的一对 Y 代表两个 Y 之间只有 X，或什么字符都没有。

首先特判两种情况：

显而易见地，
如果 $cnt_X = n$，那么直接输出 $k - 1$。
如果 $cnt_X = 0$，那么直接输出 $n - k - 1$。

接下来，我们发现，对于两个相邻的 Y，如果它们之间隔着 $a$ 个 X，那么，我们用掉 $a$ 次翻转就能对答案增加 $a + 1$ 的贡献。

举例：

对于 YXXY，原先这一段的答案为 $0$，翻转中间的 $2$ 个 X，答案变为 $3$。
对于 YXY，原先这一段的答案为 $0$，翻转中间的 $1$ 个 X，答案变为 $2$。
对于 YY，把原先这一段的答案当作 $0$，翻转中间的 $0$ 个 X，答案变为 $1$。

可见，对于任意的间隔 $a$，全部翻转后都能对答案造成 $a + 1$ 的贡献。

因此，我们需要优先翻转间隔小的一段 X，以获得最多的翻转次数，让答案尽可能大。

扫一遍整个字符串，依次把相邻的两个 Y 之间的 X 数量记录下来，最后再从小到大排序。
记得到的序列为 $A$，遍历这个序列，如果当前 $A_i \le k$，那么消耗 $A_i$ 次翻转机会，$k - A_i\to k$，并把 $Ans$ 增加 $A_i + 1$；如果 $A_i > k$，那么我们无法把一整段 X 翻转完，那么最优的一定是从左到右依次翻转，直到翻转次数用完，而每次对答案的贡献是 $1$，因此这种情况 $Ans$ 直接加 $k$。

如果遍历完了这个序列，$k$ 还有剩余，那么显而易见，答案也是直接加 $k$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 200005; // 数据范围
int n, k; // n 代表字符串长度，k 代表翻转次数
string s; // s 为输入的字符串
int cntX; // 统计输入的字符串中 X 的个数
int ans; // 记录答案的变量，初值为 0
vector<int> dis; // 两个相邻 Y 之间 X 个数的序列
int main() {
    cin >> n >> k >> s; // 读入 n, k, s
    for(int i = 0; s[i]; i ++) { // 遍历整个字符串
        if(s[i] == 'X') cntX ++; // 统计 X 的个数 
    }
    if(cntX == 0) { // 特判 1
        printf("%d\n", max(n - k - 1, 0)); // 显而易见的答案
        return 0; // 直接退出程序
    }
    if(cntX == n) { // 特判 2
        printf("%d\n", max(k - 1, 0)); // 显而易见的答案
        return 0; // 直接退出程序
    }
    if(cntX < k) { // 翻转整个字符串，n - k to k
        k = n - k; // 翻转次数也要翻转
        for(int i = 0; s[i]; i ++) {
            s[i] = 'X' + 'Y' - s[i]; // 翻转 s[i]
        }
    }
    int lst = -1; // 表示上一个 Y 的位置
    for(int i = 0; s[i]; i ++) {
        if(s[i] == 'Y') {
            if(lst != -1) { // 特判第一个 Y
                dis.push_back(i - lst - 1); // 两个相邻的 Y 之间 X 的数量
            }
            lst = i; // 更新上一个 Y 的位置
        }
    }
    sort(dis.begin(), dis.end()); // 从小到大排序
    for(int i : dis) { // 遍历序列
        if(k >= i) {
            k -= i; // 使用 i 次翻转
            ans += 1 + i; // 对答案造成 i + 1 的贡献
        }
    }
    ans += k; // 使用剩下的 k 次翻转，对答案造成 k 的贡献
    printf("%d\n", ans); // 输出答案
    return 0;
}

声明