如厕计划-题解

发表于 分类于 ， 阅读次数：

Link

toilet

思路分析

为了 \(n\) 分钟之内结束，两个厕所一刻都不能停。由于男生不能进女厕，所以一个男生必须要和一个女生一起才能上厕所（奇怪啊）。如果把男生视为 \(1\)，女生视为 \(-1\)，那么对于任意位置，后缀和必须要小于等于 \(1\) 才能保证成功。（后缀和为 \(1\) 时多出来的那个男生可以跟着他之前的女生走）。

如果出现了后缀和大于 \(1\) 怎么办呢？就需要把一些男生放到前面去。如果累计的男生个数有 \(x\) 个，则至少要放 \(x-1\) 个到女生前面，则答案应该对 \(x-1\) 取 \(\max\)。

这样的话，考虑从后往前扫描字符串，用一个变量来存储后缀和，当后缀和大于 \(1\) 时，更新一下答案。

然后考虑怎么处理重复字符串。容易想到，重复的字符串对于后缀和的影响是相同的，并且无论影响是正是负，对答案有影响的只有可能是第一个串和所有串连在一起。所以维护一个字符串产生的后缀和变化量 \(delta\) 以及变化过程中的最大变化量 \(maxdelta\)，如果一共重复 \(t\) 次，并且在这个字符串之前的后缀和是 \(cnt\)，那么在这些重复的字符串中，最大后缀和是 \(\max(cnt+maxdelta, cnt+maxdelta+delta\times(t-1))\)，而对总后缀和的影响是 \(cnt \leftarrow cnt + delta\times t\)。

最后看一下无解：如果总后缀和最终大于 \(0\)（\(1\) 也不行，如果是 \(1\) 第一个男生无法上厕所），说明男生过多了，则输出 \(-1\)。否则输出过程中的最大后缀和减一。

AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

// #define FILE_IO
namespace io {...};
using namespace io;

const int maxm = 1e5 + 5;

long long n, ans;
int m;
string s[maxm];
long long t[maxm];

int main() {
    // freopen("toilet.in", "r", stdin);
    // freopen("toilet.out", "w", stdout);
    read(n); read(m);
    for (int i = 1; i <= m; i++) {
        cin >> s[i];
        read(t[i]);
        reverse(s[i].begin(), s[i].end());
    }
    long long cnt = 0;
    for (int i = m; i >= 1; i--) {
        
        long long delta = 0, mxc = 0;
        for (int j = 0; j < s[i].size(); j++) {
            if (s[i][j] == 'F') delta--;
            else delta++;
            mxc = max(mxc, delta);
        }
        ans = max(ans, mxc + cnt);
        ans = max(ans, mxc + cnt + delta * (t[i] - 1));
        cnt += delta * t[i];
    }
    if (cnt > 0) write(-1);
    else if (ans > 1) write(ans - 1);
    else write(0);
    return 0;
}