P3615 如厕计划

$ color{#0066ff}{ 题目描述 }$

竞赛比完之后，水箱里充满水的选手们鱼贯而出。凡华中学的厕所规划的很糟，只有两个厕位，于是厕所门前排起了长长的队伍。

厕所有两个，一个是女生专用厕所，另一个是男女混用厕所。一共有2N个选手正在排队，男女生数量可能不同。如果队头的是妹子，只要某个厕所是空的就可以进入，但是如果两个厕所都是空的，那么优先进入女性专用厕所。而如果队头是个绅♂士，只有在男女混用厕所是空的时候才能使用；如果只有女性专用厕所是空的，那么队伍中最靠前的妹子就可以不用继续等直接如厕。我们假设所有人如厕都需要花1分钟，不考虑切换的时间。

然而，N分钟后，就要开饭了，所有人必须如厕完，不过看样子似乎来不及。主办方可以重新调换顺序，不过有些人会因为新的顺序中自己更加后面了而感到不满，不满度是自己相比于原队列后退了几个顺序（除此之外跟自己的实际如厕顺序无关）。

主办方发现了这一点，所以希望你帮助他们解决这个问题，设计出一种方案，对于其中不满意度最大的学生，尽可能让他的不满意度最小。你只需要告诉他门最不满意的学生的不满意度是多少。

(color{#0066ff}{输入格式})

由于人相当多，我们用几段字符串来描述这个队列。

第一行一个整数N

第二行一个整数M

接下来M行，有一个字符串Si和一个整数Ki构成，中间有空格隔开，字符串中只有'M'（男）和'F'（女）。最后的字符串就是 S1拼接K1次+ S2拼接K2次+ ... +SM拼接KM次

(color{#0066ff}{输出格式})

输出一个整数，表示答案。如果无论怎么样都没办法N分钟之内达成，请输出-1

(color{#0066ff}{输入样例})

5
3
FFF 1
M 5
FF 1

(color{#0066ff}{输出样例})

(color{#0066ff}{数据范围与提示})

原队列是FFFMMMMMFF

改进后的队列是FMMFFMMMFF

所以厕所会按照下面的时间使用：

分钟 1   2   3   4   5
共用 2   3   6   7   8
女用 1   4   5   9   10

两个妹子往后面移动了2位，所以不满意度是2

20% N<=10;M=1;K1=1

40% N<=100000;M=1;K1=1

100% 1<=N,Ki<=10^18;1<=M<=100000;所有Si字符串长度之和不超过200000

(color{#0066ff}{题解})

什么时候会浪费时间？两个男的等厕所！会有一个厕所闲置。。

所以男的应该尽量靠前，且不能有超过n个男的，要不然就无解了

我们从末尾计算后缀和，男-1女1,一旦后缀和到达了-2，那么就会有两个男的决定谁去女厕的局面（雾

所以我们只要保证后缀和一直大于-2就行

因此，我们让每个女生向后走ans位，使得后缀和一直大于-2

于是我们只需记录一个后缀最小值，把它抬到-1就行了

实现时可以男女正负互换，取最大后缀，其实是一样的

#include<bits/stdc++.h>
#define LL long long
LL in() {
	char ch; LL x = 0, f = 1;
	while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
	return x * f;
}
const int maxn = 2e5 + 10;
std::vector<char> v[maxn];
LL len[maxn];
LL max[maxn], ss[maxn];
char s[maxn];
LL num[maxn];
LL n, m, ans, now;
int main() {
	n = in(), m = in();
	LL tot = 0;
	for(int i = 1; i <= m; i++) {
		scanf("%s", s);
		v[i].push_back('$');
		for(char *p = s; *p; p++) v[i].push_back(*p);
		for(int j = v[i].size() - 1; j >= 1; j--) {
			ss[i] += (v[i][j] == 'F'? -1 : 1);
			max[i] = std::max(max[i], ss[i]);
		}
		tot += (num[i] = in()) * ss[i];
	}
	if(tot > 0) return puts("-1"), 0;
	ans = 1;
	for(int i = m; i >= 1; i--) {
		if(ss[i] > 0) ans = std::max(ans, now + (num[i] - 1) * ss[i] + max[i]);
		else ans = std::max(ans, now + max[i]);
		now += ss[i] * num[i];
	}
	printf("%lld", ans - 1);
	return 0;
}