题目大意
给定一个长度为 \(n\) 的、只有 O 和 L 组成的字符串，求出一个 \(i\)，使得 \(i\) 左侧和右侧 O、L 的数量互不相等且每侧至少有一个 O 和一个 L。
思路
注意 \(n\) 的范围是 \(2 \le n \le 200\)，数据范围很小，暴力的时间复杂度是可以接受的。
暴力的想法很简单，就是预处理出 \(i\) 为任意值时字符串左侧 O 和 L 的数量，再用一个循环做判断即可。
对于求右侧 O 和 L 的数量，可以用 \(i = n\) 时的数量减去 \(i\) 的数量。
代码
#include <bits/stdc++.h>
#define il inline
using namespace std;
const int N = 205;
int n, ocnt[N], lcnt[N];
char s[N];
int main() {
scanf("%d%s", &n, s + 1);
ocnt[0] = lcnt[0] = 0;
for (int i = 1; i <= n; i++) {
ocnt[i] = ocnt[i - 1], lcnt[i] = lcnt[i - 1];
if (s[i] == 'O') ocnt[i]++;
if (s[i] == 'L') lcnt[i]++;
}
for (int i = 1; i <= n; i++) {
int ot = ocnt[n] - ocnt[i], lt = lcnt[n] - lcnt[i];
if (ocnt[i] != ot && lcnt[i] != lt && (ot != 0 || lt != 0) && (ocnt[i] != 0 || lcnt[i] != 0)) {
printf("%d\n", i);
return 0;
}
}
printf("-1\n");
return 0;
}
注意在做判断时不要忘记判两侧的字符串是否都至少有一个
O和一个L。