JOIOI 塔

NC53185. JOIOI 塔

描述

本题译自 JOI 2013 Final T4「JOIOIの塔」

JOIOI塔是一种单人游戏。
这个游戏要用到一些写有J,O,I中任一文字的圆盘。这些圆盘的直径互不相同。游戏开始时，这些圆盘按照直径大的在下面的规则堆叠。你需要用这些圆盘做尽量多的迷你JOIOI塔。迷你JOIOI塔由3个圆盘构成，从直径较小的圆盘开始分别为J,O,I或分别为I,O,I。不过，每个圆盘最多只能使用一次。

任务
给出长为N的字符串S，表示直径从小到大的圆盘上的文字。请编写程序求出使用这些圆盘能够做出的迷你JOIOI塔个数的最大值。

输入描述

第一行为一个整数$N$，表示字符串$S$的长度。第二行是一个字符串$S$。

输出描述

输出一行一个整数：表示能够做出的迷你JOIOI塔数量的最大值。

示例1

输入:

6
JOIIOI

输出:

说明:

JOIIOI分别含子串JOI和子串IOI各一个，故可以做出2个迷你JOIOI塔。

示例2

输入:

5
JOIOI

输出:

说明:

虽然JOIOI也分别含子串JOI和子串IOI各一个，但每个字符不能被使用两次或以上。

示例3

输入:

6
JOIOII

输出:

说明:

此样例对应题目描述中的例子。

示例4

输入:

15
JJOIIOOJOJIOIIO

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 148ms, 内存消耗: 1384K, 提交时间: 2022-08-08 17:23:48

#include <bits/stdc++.h>
using namespace std;
int l = 0, r, ans = 0, n;
char s[1000005];
bool check(int x) {
    int ans = 0, tot = 0, cnt = 0;
    for (int i = n; i; i--) {
        if (x == ans)
            return 1;
        if (s[i] == 'J') {
            if (tot)
                tot--, ++ans;
            continue;
        }
        if (s[i] == 'O') {
            if (cnt)
                --cnt, ++tot;
            continue;
        }
        if (s[i] == 'I') {
            if (ans + tot + cnt < x)
                cnt++;
            else {
                if (tot)
                    tot--, ans++;
            }
        }
    }
    if (x == ans) {
        return 1;
    }
    return 0;
}

int main() {
    scanf("%d%s", &n, s + 1);
    r = n;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid))
            ans = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    printf("%d", ans);
}

上一题

下一题

详情