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

zhujianheng · 2025-11-19 10:04:33 · 题解

我们首先显然的，知道一个队列如果是合法的（就是可以在时间内实现出的），则设男生为 -1，女生为 1，后缀和永远小于 2（因为男多女少是不可能合法的）。

首先判无解。总后缀和大于等于 2 时显然不行。如果是 1 呢？那么第一个男生就会出现矛盾，所以只要总后缀和为正数就不行。

然后如果有解，怎么计算答案？很显然，只要将最后面的男生调整到前面去，使得最大的后缀和也不超过 1 就行，每次调整一位男生时，维护一个字符串的变化量 s_i，则对整体后缀和的贡献为 s_i \times k_i，对最大字符串的变化量的贡献为 \max(mx_i,mx_i+(k_i-1) \times s_i)，其中 mx_i 为最大后缀和，s_i 为单次变化量，k_i 为拼接的字符串个数。

最后代码很清晰了。

#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;
}