CodeForces 650B Image Preview

Posted on By 二价氢

题目大意

有\(n\)个格子围成环,如果两个相邻的格子间移动需要\(a\)秒,浏览一个格子需要1秒,如果一个格子上写的是h就要额外花\(b\)秒,第二次浏览不需要花任何时间。问在\(T\)秒内最多能浏览多少个格子。

做法

我们可以YY出来,只可能是下面几种情况之一:

  1. 一直顺时针走
  2. 一直逆时针走
  3. 顺时针走,然后调头
  4. 逆时针走,然后调头

依次枚举就好……注意到如果我们往一个方向走得多,那么调头就必然走得少一些,基于这种情况,我们可以用单调性来实现在\(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;
}