CFR 650 B. Image Preview ( Two Pointers )

Problem - B - Codeforces

題意：
有 N 張照片，成環形，第一張的左邊是第 N 張。一開始在第一張照片，如果照片是 'w' 就必須花 B 秒將它變成 'h' 才能觀賞，觀賞要 1 秒，向左或向右滑都要 A 秒。但如果當前的照片還沒有觀賞過，不能滑動。求最佳方案下 T 秒內最多可以看幾張照片。

資料規模：
1 ≤ n ≤ 5e5
1 ≤ a, b ≤ 1000
1 ≤ T ≤ 1e9

解法：
很顯然，最多只會改變一次滑動方向，不可能向左向右後右向左是最佳方案。因次先將右邊當作是最後的方向，枚舉走多遠，再用另一個指針維護對應能向左走多遠折返回來。

時間 / 空間複雜度：
O( N )

int N, A, B, T;
string seq;

void init(){
  cin >> N >> A >> B >> T;
  cin >> seq;
}

int ans = 0;

void preprocess(){
  int t = 0, ptr = N;
  for( int i = N - 1; i >= 0; --i ){
    if( t + 2 * A + B * ( seq[ i ] == 'w' ) + 1 > T ){
      break;
    }
    t += 2 * A + B * ( seq[ i ] == 'w' ) + 1;
    --ptr;
  }
  for( int i = 0; i < N; ++i ){
    while( t + B * ( seq[ i ] == 'w' ) + 1 > T and ptr < N ){
      t -= B * ( seq[ ptr ] == 'w' ) + 1 + 2 * A;
      ++ptr;
    }
    if( t + B * ( seq[ i ] == 'w' ) + 1 > T ){
      break;
    }
    t += B * ( seq[ i ] == 'w' ) + 1 + A;
    upmax( ans, i + 1 + N - ptr );
  }
  upmin( ans, N );
}

void solve(){
  cout << ans << endl;
}