题目理解

我们需要从字符串 $S$ 中构造尽可能多的迷你 JOIOI 塔，每个塔由3个字符组成，有两种合法模式：

• JOI（J→O→I）
• IOI（I→O→I）

重要限制：每个字符只能使用一次。

关键点：字符串 $S$ 表示直径从小到大的圆盘，但题目说游戏开始时圆盘按直径大的在下面堆叠，而我们需要构造的塔是从小直径开始。因此代码中先将字符串反转，这样我们从大直径到小直径处理。

算法思路

1. 问题转化

由于有两种塔模式：

• JOI 模式：需要 J, O, I 各一个
• IOI 模式：需要 I, O, I（两个I和一个O）

我们可以将问题转化为：能否构造 $k$ 个塔？

2. 二分答案

答案显然在 $[0, \frac{N}{3}]$ 范围内，我们可以二分答案，检查是否能构造 $mid$ 个塔。

3. 贪心检查策略

从大直径到小直径处理字符（即反转后的字符串顺序）：

我们维护几个计数器：

• tI：可用的 I 数量（用于组成 JOI 或 IOI）
• tO：可用的 O 数量
• tb：已使用的 I 数量（用于 IOI 模式的第一个 I）
• sum：已完成的塔数量

处理规则：

• 遇到 J：如果有可用的 O，就消耗一个 O 完成一个塔（J 是最后一个字符）
• 遇到 O：如果有可用的 I，就消耗一个 I 变成可用的 O
• 遇到 I：
  • 如果 tb < k（还能为 IOI 模式预留 I），就增加可用的 I
  • 否则，如果有可用的 O，就消耗一个 O 完成一个塔（这是 IOI 模式的第二个 I）

代码解析

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

int main() {
    int n;
    scanf("%d", &n);
    string s;
    cin >> s;
    reverse(s.begin(), s.end());  // 反转字符串，从大直径开始处理
    
    auto check = [&](const int &val)->bool {
        int tI = 0, tO = 0, tb = 0, sum = 0;

        for (auto ch : s) {
            if (ch == 'J') {
                if (tO)          // 有O可用，完成一个塔
                    tO--, sum++;
            } else if (ch == 'O') {
                if (tI)          // 有I可用，转换成O
                    tI--, tO++;
            } else {  // ch == 'I'
                if (tb < val)    // 还能为IOI模式预留I
                    tI++, tb++;
                else {           // 预留已满，尝试完成塔
                    if (tO)
                        tO--, sum++;
                }
            }
        }
        return sum >= val;  // 能否完成val个塔
    };
    
    int l = 1, r = n / 3, ans = 0;
    // 二分答案
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    
    printf("%d\n", ans);
    return 0;
}

算法正确性分析

为什么贪心策略有效？

1. 从大直径到小直径处理：确保我们优先使用"下面"的圆盘，符合堆叠规则
2. 优先为 IOI 模式预留 I：因为 IOI 需要两个 I，是更稀缺的资源
3. J 直接消耗 O 完成塔：J 只能作为塔的结尾，有 O 就立即使用

状态转移逻辑

• I → tI：可作为 JOI 的 I 或 IOI 的第一个 I
• O + tI → tO：将 I 转换成可用的 O
• J + tO → 完成塔
• I + tO → 完成塔（IOI 的第二个 I）

复杂度分析

• 二分答案：$O(\log N)$ 次检查
• 每次检查：$O(N)$ 遍历字符串
• 总复杂度：$O(N \log N)$，对于 $N \leq 10^6$ 可接受

样例验证

样例1：JOIIOI（反转后：IOIIOJ）

• 检查 $k=2$：成功
• 过程：I(预留)→O(转换)→I(预留)→I(完成塔)→O(转换)→J(完成塔)

样例2：JOIOI（反转后：IOIOJ）

• 检查 $k=2$：失败，只能完成1个塔