[JOI 2013 Final]JOIOI 塔

[JOI 2013 Final]JOIOI 塔

题意

给出一个由 \(\text{JOI}\) 组成的字符串，可从中取出一些子序列。

求最多取出多少 \(\text{IOI}\) 和 \(\text{JOI}\)。

思路

若答案 \(x\) 可行，则所有 \(y<x\) 均可行，

若答案 \(x\) 不可行，则所有 \(y>x\) 均不可行。

这样就可以可行性二分。

考虑如何判断答案 \(x\) 是否可行。

\(\text{JOI}\) 和 \(\text{IOI}\) 都有 \(\text{OI}\)。

发现 \(\text{J}\) 只能用来拼 \(\text{JOI}\) 的第一位，\(\text{O}\) 只能用来拼 \(\text{OI}\)。

而问题就在于 \(\text{I}\)，既可以用来做 \(\text{IOI}\) 的第一位，也可以用来拼 \(\text{I}\)。

从后往前扫描字符串，同时维护 \(\text{I,O,J,OI,JOI,IOI}\) 的个数。

如果扫到 \(\text{J,O}\)，将对应的个数加一，如果可以就拼接成为 \(\text{JOI,OI}\)。

对于 \(\text{I}\)，我们需要的 \(\text{OI}\) 只有 \(x\) 个，若当前拼出的 \(\text{OI}\) 总数小于 \(x\)，就拼 \(\text{OI}\)，否则和 \(\text{OI}\) 拼接出 \(\text{IOI}\)。

如果最后的 \(\text{JOI,IOI}\) 总数大于等于 \(x\) 则可行。

代码

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

const int N = 1e6 + 5;

int n;
char S[N];

bool check(int x) {
	int JOI = 0, IOI = 0, OI = 0;
	int J = 0, O = 0, I = 0;
	for (int i = n; i >= 1; i --) {
		if (S[i] == 'I') {
			I ++;
			if (OI + JOI + IOI + I - 1 >= x && OI > 0) {
				I --;
				OI --;
				IOI ++;
			}
		}
		if (S[i] == 'O') {
			O ++;
			if (I > 0 && O > 0) {
				O --;
				I --;
				OI ++;
			}
		}
		if (S[i] == 'J') {
			J ++;
			if (J > 0 && OI > 0) {
				J --;
				OI --;
				JOI ++;
			}
		}
	}
	return JOI + IOI >= x;
}

int main() {
freopen("joi.in","r",stdin);
freopen("joi.out","w",stdout);
	scanf("%d", &n);
	scanf("%s", S + 1);
	
	int l = 0, r = n, mid, res;
	
	while (l <= r) {
		mid = (l + r) >> 1;
		if (check(mid)) {
			res = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	} 
	
	cout << res << "\n";
	return 0;
}