luogu P12443 题解

题目描述：

我们需要将一排食物分成两部分：一个前缀和一个后缀。需要满足以下条件：

• 前缀和后缀都至少有一个食物。

• 前缀中的面包数量不等于后缀中的面包数量。

• 前缀中的洋葱数量不等于后缀中的洋葱数量。

思路：

先遍历处理字符串中面包和洋葱的总数，然后遍历所有可能的分割点：对于每一个可能的分割点 $k$，计算前缀和后缀中的 $\text{L}$ 和 $\text{O}$ 的数量。最后对每个 $k$ 检查是否满足：

• 前缀的 $\text{L}$ 数量是否等于后缀的 $\text{L}$ 数量。

• 前缀的 $\text{O}$ 数量是否等于后缀的 $\text{O}$ 数量。

如果找到满足条件的 $k$，立即输出。如果遍历完所有 $k$ 都没有找到则输出 $-1$。

Code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int now, now1;
int cnt, cnt1;
int l = 0, o = 0;
string s;

signed main() {
	cin >> n >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'L') {
			l++;
		} else {
			o++;
		}
	}
	for (int k = 1; k < n; ++k) {
		if (s[k - 1] == 'L') {
			cnt++;
		} else {
			cnt1++;
		}
		now = l - cnt, now1 = o - cnt1;
		if (cnt != now && cnt1 != now1) {
			cout << k;
			exit(0);
		}
	}
	cout << -1;
	return 0;
}