題意：給你n個照片，從第一個照片開始看，如果一張照片是'w'，那么要花費b時間去反轉他，否則不用反轉，看一張從來沒看過的照片要1時間， 從一張滑動到另一張要a時間。如果一張照片看過，則不用再反轉，也不用再傻1s。求在不超過T時間的前提下最多能看多少張。
思路：首先模擬這個選著過程，這里引入兩個指針，lr代表從起點開始從右遍歷，ll代表從后遍歷到最后一個符合條件的位置，ll到lr之間串如果符合題意則求ans。
注意ll和lr之間一定不超過n。
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <algorithm> 5 #include <cmath> 6 #include <cstdlib> 7 using namespace std; 8 const double pi=acos(-1); 9 const int maxn=500010; 10 char str[maxn]; 11 int s[2*maxn];//二倍空間：0到n-1是往后遍歷，n到2*n-1是往前遍歷 12 13 int main() { 14 int n,a,b,t; 15 while(~scanf("%d%d%d%d",&n,&a,&b,&t)) { 16 scanf("%s",str); 17 int sum=0; 18 for(int i=0; i<n; i++) { 19 if(str[i]=='w') 20 s[i]=s[i+n]=b+1; 21 else 22 s[i]=s[i+n]=1; 23 sum+=s[i]; 24 } 25 sum-=s[0]; 26 int ll=1,lr=n; 27 int ans=0; 28 while(ll<=n&&lr<2*n) { 29 sum+=s[lr++]; 30 while(lr-ll>n||sum+(lr-ll-1+min(lr-n-1,n-ll))*a>t) { 31 sum-=s[ll++]; 32 } 33 ans=max(ans,lr-ll); 34 } 35 cout<<ans<<endl; 36 } 37 return 0; 38 }
?
