题目大意
有\(n\)个格子围成环,如果两个相邻的格子间移动需要\(a\)秒,浏览一个格子需要1秒,如果一个格子上写的是h就要额外花\(b\)秒,第二次浏览不需要花任何时间。问在\(T\)秒内最多能浏览多少个格子。
做法
我们可以YY出来,只可能是下面几种情况之一:
- 一直顺时针走
- 一直逆时针走
- 顺时针走,然后调头
- 逆时针走,然后调头
依次枚举就好……注意到如果我们往一个方向走得多,那么调头就必然走得少一些,基于这种情况,我们可以用单调性来实现在\(O(N)\)的复杂度内解决问题。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500000 + 5;
long long a, b, t;
long long leftT[maxn];
long long rightT[maxn];
char str[maxn];
int n, ans;
int main() {
ios::sync_with_stdio(0);
cin >> n >> a >> b >> t >> str;
str[n] = str[0];
for (int i = 0; i < n; i++) {
if (i)
rightT[i] = rightT[i - 1] + a;
rightT[i] += b * (str[i] == 'w') + 1;
if (rightT[i] <= t)
ans = max(ans, i + 1);
}
for (int i = n; i > 0; i--) {
if (i != n)
leftT[i] = leftT[i + 1] + a;
leftT[i] += b * (str[i] == 'w') + 1;
if (leftT[i] <= t)
ans = max(ans, n - i + 1);
}
int lt = 1, rt = n - 1;
for (int i = 0; i < n; i++) {
while (a * i + leftT[lt] + rightT[i] - rightT[0] > t && lt < n)
lt++;
if (a * i + leftT[lt] + rightT[i] - rightT[0] <= t && lt < n)
ans = max(ans, i + 1 + n - lt);
}
for (int i = n; i > 0; i--) {
while (a * (n - i) + leftT[i] + rightT[rt] - rightT[0] > t && rt > 0)
rt--;
if (a * (n - i) + leftT[i] + rightT[rt] - rightT[0] <= t && rt > 0)
ans = max(ans, n - i + 1 + rt);
}
ans = min(ans, n);
cout << ans << endl;
return 0;
}