Codeforces Round #345 (Div. 2) D. Image Preview __ two pointers and pretreat

My Solution

This is really a good problem for me ☺☺

pretreat whhw......  to array val[maxn] when read the test data

then use two pointers to find the maximum number of photos Vasya is able to watch during those T seconds.

if a is really small, we can go right and come back , go left, then we can go right again. But for the final result it is only come back once,

so we just make it that  it is only come back once in the progress.

1.go right first

//if this progress end,and sum == T, it's a hard problem to solve,★★ please read my code for more details.

2.then r--, l--;the left pointer begin to move towards the left

3.if r == 0 when break the while above , we are supposed to run r = 0, l = 0,sum = 0; l-- to go left.

#include 
#include 
#include 
using namespace std;
const int maxn = 5*1e5 +8;
int val[maxn];


int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    memset(val, 0, sizeof val);       //initial the array will make the program running faster
    int n, a, b, T;
    char ph;
    scanf("%d%d%d%d", &n, &a, &b, &T);
    getchar();
    for(int i = 0; i < n; i++){
        scanf("%c", &ph);
        if(i == 0) {if(ph == 'w') val[0] = b+1; else val[0] = 1;}
        else{
            if(ph == 'w') val[i] = b+a+1;
            else val[i] = a+1;
        }
        //cout<<val[i]<<" ";
    }
    //cout<<endl;
    //two pointers,
    //If Vasya has already opened the photo, he just skips it
    //(so he doesn't spend any time for watching it or for changing its orientation).
    //but it will only get back once, unless it will wast time which is not necessary.
    int l = 0, r = 0, sum = 0;
    int ans = -1;
    //go rights first
    while(sum < T && r < n){ sum += val[r++]; //!from WA13 to Accepted if(sum > T ) r--;       //!if sum == T  we can't r-- (but at line44 sum -= val[r];we should add if(sum != T) before),
                                //! unless line41 ans = max(ans,(r-0)); and line45 r--;  will be wrong.
    }                           //!the last time has r++, and this val[r] is not added to sum
    ans = max(ans,(r-0));    // r-0+1 -1
    //if(sum == T) ans++; this is not enough  and r should r++             //!!!!!!   this two place
    if(ans > n) ans = n;
    if(sum != T)sum -= val[r];  //!so if(sum == T) we shouldn't run the sentence sum -= val[r];
    r--;                        //!but here we should do as the normal time
    /* above can also be wrote as here
    sum += val[0];
    while(sum < T && r < n){ r++;sum += val[r]; } if(sum == T) r++; //Oh almost the same ans = max(ans,(r-0)); if(ans > n) ans = n;
    if(sum != T)sum -= val[r];
    r--;
    */

    //cout<<ans<<endl; //then left , the one short is is the direction the pointer go back bool first = true; // first time from l to r -> r to l
    while(ans != n && ans != 0){
        while(sum <= T && -l + r <= n-1 && l > -n){        //!!!!!!l > r-n-1 and at the same time l > -n   otherwise maybe TLE
            l--; sum += val[(l + n)%n];  //!!!!!!i-- ,first    from WA5 to WA7
            if(-l < r && first) sum += a;
            else {if(first){sum -= a*(-l - 1);sum += a*r; first = false;} }              // this will happen only once
            //!!!!!! a*(-l - 1)  not a*(-l) because the last time sum didn't add a 'a'   from WA5 to WA7
        }
        if(sum < T) break; ans = max(ans,(r-l)); //! r + -l - 1 + 1 if(first)sum -= val[r]; else sum -= (val[r] + a); if(r>0) r--;
        if(r == 0) break;              //!!!!!!   r not be r <= 0       from WA7 to WA8

    }

    //!!!!!!   for r == 0                                              from WA8 to WA13
    if(r == 0){
        l = 0, sum = 0;
        sum += val[0];
        while(sum < T && l > -n){
            l--; sum += val[(l + n)%n];
        }
        if(sum == T) l--;
        ans = max(ans,(0-l));
        if(ans > n) ans = n;
    }
     printf("%d", ans);
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx