专栏文章

题解：P3615 [JOISC 2016] 如厕计划 / Toilets

zzhujianheng
P3615题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min57dun
此快照首次捕获于
2025/12/01 20:45
3 个月前
此快照最后确认于
2025/12/01 20:45
3 个月前
查看原文
我们首先显然的，知道一个队列如果是合法的（就是可以在时间内实现出的），则设男生为 −1-1，女生为 11，后缀和永远小于 22（因为男多女少是不可能合法的）。
首先判无解。总后缀和大于等于 22 时显然不行。如果是 11 呢？那么第一个男生就会出现矛盾，所以只要总后缀和为正数就不行。
然后如果有解，怎么计算答案？很显然，只要将最后面的男生调整到前面去，使得最大的后缀和也不超过 11 就行，每次调整一位男生时，维护一个字符串的变化量 sis_i，则对整体后缀和的贡献为 si×kis_i \times k_i，对最大字符串的变化量的贡献为 max⁡(mxi,mxi+(ki−1)×si)\max(mx_i,mx_i+(k_i-1) \times s_i)，其中 mximx_i 为最大后缀和，sis_i 为单次变化量，kik_i 为拼接的字符串个数。
最后代码很清晰了。
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100009;
string s[N];
int k[N], n, m, ans, suf[N], mx[N];

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		cin >> s[i] >> k[i];
	int x = 0;
	for (int i = m; i; i--) {
		for (int j = s[i].size() - 1; ~j; j--) {
			if (s[i][j] == 'M')
				suf[i]++;
			else
				suf[i]--;
			mx[i] = max(mx[i], suf[i]);
		}
		x += suf[i] * k[i];
	}
	if (x > 0) {
		cout << -1 << '\n';
		return 0;
	}
	int ans = 0;
	x = 0;
	for (int i = m; i; i--) {
		ans = max(ans, max(x + mx[i], x + (k[i] - 1) * suf[i] + mx[i]));
		x += suf[i] * k[i];
	}
	cout << (ans?ans - 1:0) << endl;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...