题解：P12443 [NERC2023] LOL Lovers

weiyi_xiaohao · 2025-05-25 20:14:50 · 题解

题解：P12443 [NERC2023] LOL Lovers

题目大意

给定一个长度为 n 的字符串，字符串中只会包含下列两种字符。

• 用字母 \texttt{O} 表示洋葱。
• 用字母 \texttt{L} 表示面包。

按照以下要求输出 k。

• 以 k 分开，字符串前缀的洋葱和面包的数量不等于后缀洋葱和面包的数量，并且前缀、后缀的长度至少为 1。
• 如果不存在一个合法的 k，输出 -1。
• 数字 k 可以为任意数，但必须满足要求。

思路

由于 k 没有太多的限制，因此我们如果找到了一个合法的位置，直接输出该位置即可。

遍历结束，不存在合法的答案，代码结尾应输出 -1。

设前缀为 0 到 i-1，后缀为 i 到 n-1，我们只需用循环处理前缀、后缀中字母 \texttt{O} 和 \texttt{L} 的数量，然后比较即可。

代码

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

int main() {
    int left_o, left_l, right_o, right_l, n;
    string s;
    cin >> n >> s;
    for (int i = 1; i <= n - 1; i++) { //遍历字符串的每一位
        left_o = 0, left_l = 0, right_o = 0, right_l = 0; //初始化
        for (int j = 0; j <= i - 1; j++) { //统计前缀
            if (s[j] == 'O') {
                left_o++;
            } else {
                left_l++;
            }
        }
        for (int j = i; j <= n - 1; j++) { //统计后缀
            if (s[j] == 'O') {
                right_o++;
            } else {
                right_l++;
            }
        }
        if (left_o != right_o && left_l != right_l && left_o + left_l > 0 && right_o + right_l > 0) {
            //如果前、后缀字母O和L的数量不等
            cout << i; //输出该位置
            return 0; //结束程序
        }
    }
    cout << -1; //不可能存在答案
    return 0; //完结
}