JOI2013 JOIOI の塔 （Tower of JOIOI）题解

· · 题解

Description

给定一个由 J、O、I 组成的字符串，求最多能拆分成多少 JOI 或 IOI。

对于所有数据，1\leq \vert S\vert\leq 10^6。

Solution

先处理出 \text{pre}_i 为前缀 J 和 I 的数量，即能组成多少个头部。

然后倒着做，维护当前拼出的 I、OI 和最终成品的数量。遇到 J、O 就模拟拼接，遇到 I 判断当前的 \text{pre}_i 是否小于等于 I、OI 的总数量，若成立就拼成 IOI，否则作为 I。

判断这个是因为 I 可以作为最后的 I 也可以作为开头的 I。若大于等于前缀 J、I 数量则作为最后的 I 数量够用，无需继续拼接了。

时间复杂度 \mathcal{O}(n)。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Milkcat {
    const int N = 2e7 + 5;
    int n, ow, w, tot, pre[N]; char s[N];
    int main() {
        cin >> n >> (s + 1);
        for (int i = 1; i <= n; i ++)
            pre[i] = pre[i - 1] + (s[i] == 'J' || s[i] == 'I');
        for (int i = n; i >= 1; i --) {
            if (s[i] == 'J' && ow) ow --, tot ++;
            if (s[i] == 'O' && w) w --, ow ++;
            if (s[i] == 'I') {
                if (ow + w >= pre[i] && ow) ow --, tot ++;
                else w ++;
            } 
        }
        cout << tot << '\n';
        return 0;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}

/*
15
NNOWWOONONWOWWO
*/