CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
权限题所以把题面也贴出来。
Time Limit: 10 Sec Memory Limit: 512 MB
Description
有 n 个人在轮流玩赌博机，一开始编号为 i 的人有 a[i]元钱。赌博机可以抽象为一个长度为 m 的仅包含 1 和-1 的序列，若抽到 1，那么你将得到 1 块钱；若抽到-1，你将输掉 1 块钱。 第 1 局，第 1 个人会抽到序列中的第 1 项；第 2 局，第 2 个人会抽到序列中的第 2 项；第 3 局，第 3 个人会抽到序列中的第 3 项……即：第 i 个人抽完后轮到第 i+1 个人去抽，特别地，第 n 个人抽完后轮到第 1 个人去抽。序列第 i 项被抽到之后，下一个被抽到的将会是第 i+1 项，特别地，序列第 m 项被抽到之后，下一个被抽到的将会是第 1 项。 如果在某一轮，有个人输光了所有的钱，那么这场赌博游戏就会结束，请求出游戏在哪一轮结束，或者判断这个游戏会永远进行下去。
Input
第一行包含一个正整数 n(1<=n<=1000000)，表示玩家的个数。 第二行包含 n 个正整数 a[1],a[2],…,a[n](1<=a[i]<=1000000)，依次表示每个玩家一开始持有的钱数。 第一行包含一个正整数 m(1<=m<=1000000)，表示序列的长度。 第四行包含一个长度为 m 的仅包含 W 和 P 的字符串，表示这个序列，其中 W 表示 1，P 表示-1。
Output
若游戏会永远进行下去，输出-1。否则输出游戏在哪一轮结束。
Sample Input
1
2
3
4
4
2 3 2 1
3
WPP
Sample Output
1
12
代码
把队列和栈用全用数组模拟也只能跑 7800ms，status 里面最快的神仙只跑了 2600ms 不知道怎么做到的…
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pil;
const ll N=2e6+7,INF=1e18;
struct MonotoneQueue:deque<pil>
{
void push(pil p,int k)
{
while(!empty()&&back().second>=p.second)pop_back();
for(push_back(p); p.first-front().first>=k;)pop_front();
}
};
char s[N];
ll ans=INF;
int n,m,a[N],vis[N],mn[N],sum[N],pre[N<<1];
int main()
{
scanf("%d",&n);
for(int i=0; i<n; ++i)scanf("%d",&a[i]);
scanf("%d%s",&m,s);
for(int k=0; k<m; ++k)
if(!vis[k])
{
MonotoneQueue q;
vector<int> v;
for(int i=k; !vis[i]; i=(i+n)%m)v.push_back(i),vis[i]=1;
for(int i=0; i<2*v.size(); ++i)
{
q.push(pil(i+1,sum[i+1]=sum[i]+(s[v[i%v.size()]]=='W'?1:-1)),v.size()+1);
if(i>=v.size())mn[i-v.size()+1]=sum[i-v.size()]-q.front().second;
}
for(int i=2*v.size(); pre[sum[i]+N]=i; --i)
if(i<=v.size())
for(int j=v[i-1]; j<n; j+=m)
if(sum[v.size()]<0||a[j]<=mn[i])
{
ll step;
if(a[j]<=mn[i])step=pre[sum[i-1]-a[j]+N]-i+1;
else
{
ll lop=(a[j]-mn[i]-1)/(-sum[v.size()])+1;
step=lop*v.size()+pre[sum[i-1]-a[j]-lop*sum[v.size()]+N]-i+1;
}
ans=min(ans,j+1+n*(step-1));
}
}
printf("%lld",ans<INF?ans:-1LL);
}