题面太长，放不下

LOJ 2734

Description

有2n2n个人排队上厕所。厕所只有两个单间，一个男女通用，一个女性专用。所有人都排成一队

  • 若当前队首是女性，她会优先进入女性专用单间，如果已经被占用则进入男女通用单间；如果男女通用单间也被占用就只好等着了
  • 如果当前队首是男性，他会尝试进入男女通用单间，如果已经被占用他就会继续等待。此时如果女性专用单间为空，当前队列里最前的一位女性会直接进入

假设每个人上厕所需要一个单位的时间，在队列中移动的时间忽略不计。你希望调整队列顺序使得在nn个单位时间内所有人都上完厕所。

调整顺序可能会引起不满，一个人的不满值定义为调整队列前在他之后且调整队列后在他之前的人数，你希望使得所有人中最大的不满值尽可能小。求这个最小值

注：队列以一种特殊的形式给出

给出一个正整数mm，接下来mm行，每行一个字符串SS和一个数字xx,这一行描述的字符串为给出的字符串重复xx次后得到的字符串SS。把每一行描述的字符串接起来即可得到描述整个队列的字符串

描述整个队列的字符串按队列从前到后的顺序依次给出每个人的性别,MM 表示男性,FF 表示女性

Constraints

n≤1018,m≤105,∑∣S∣≤2×105n\le 10^{18}, m\le 10^5, \sum|S|\le 2\times 10^5

Solution

首先不难发现，最优策略肯定是尽量把男生往前移

考虑把男生看成−-1，女生看成11，那么只要某个队列后缀和的最小值大于等于​−1-1，这个队列就一定能在nn分钟内解决

于是我们就只需要移动后缀和最小的那个后缀中的男生，把他们尽量往前移就行了

具体细节见代码，代码很好理解

Code

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 2e5 + 100;

LL N, M, tot_F;
LL Suf[Maxn], Min[Maxn], Mul[Maxn];
// Suf : 后缀和
// Min : 单次后缀最小值
char A[Maxn];

inline void Solve ()
{
	if (tot_F < N) { puts("-1"); return ; }

	LL sum = 0, ans = LLONG_MAX;
	for (int i = M; i; --i)
	{
		if (Suf[i] < 0) Chkmin (ans, sum + Min[i] + Suf[i] * (Mul[i] - 1));
		else Chkmin (ans, sum + Min[i]);
		sum += Suf[i] * Mul[i];
	}

	if (ans >= 0) puts("0");
	else printf("%lld\n", -ans - 1);
}

inline void Input ()
{
	N = read<LL>(), M = read<int>();
	for (int i = 1; i <= M; ++i)
	{
		scanf("%s", A); Mul[i] = read<LL>();
		int len = strlen(A) - 1;
		Min[i] = LLONG_MAX;
		for (int j = len; ~j; --j)
		{
			if (A[j] == 'F') ++Suf[i], tot_F += Mul[i];
			else --Suf[i];
			Chkmin(Min[i], Suf[i]);
		}
	}
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("queue.in", "r", stdin);
	freopen("queue.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}