奶牛拍照

柿子饼同学

题解看不懂 , 思路大概是把白的看成 -1 , 把花的看成 1 , 枚举区间范围 , 用前缀和判断 , 如果白的比花的多就行 (PS 只能把白的 P 成花的 , 不能反着来)

1. #include<cstdio>
   
2. #include<cstring>
   
3. #include<iostream>
   
4. #include<algorithm>
   
5. using namespace std;
   
6. #define M 100005
   
7. int n;
   
8. struct ss{
   
9.     int pos,f;
   
10. }A[M];
    
11. int last[M<<1];
    
12. bool cmp(ss a,ss b){
    
13.     return a.pos<b.pos;
    
14. }
    
15. int main(){
    
16.     scanf("%d",&n);
    
17.     for(int i=1;i<=n;i++){
    
18.         char a[5];
    
19.         scanf("%d %s",&A[i].pos,a);
    
20.         A[i].f= a[0]=='S'?1:-1;//可以把 'W' into  'S' 即-1变成+1  多了2 故last[i]=min(last[i],last[i+2])
    
21.     }
    
22.     sort(A+1,A+1+n,cmp); // 下面就不知道什么意思了 , 求解
    
23.     memset(last,127,sizeof(last));
    
24.     int sum=n;
    
25.     last[sum]=A[1].pos;
    
26.     for(int i=1;i<n;i++){
    
27.         sum+=A[i].f;
    
28.         last[sum]=min(last[sum],A[i+1].pos);
    
29.     }
    
30.     for(int i=n<<1;i>=0;--i)last[i]=min(last[i],last[i+2]);
    
31.     sum=n;
    
32.     int ans=0;
    
33.     for(int i=1;i<=n;i++){
    
34.         sum+=A[i].f;
    
35.         ans=max(ans,A[i].pos-last[sum]);
    
36.     }
    
37.     printf("%d\n",ans);
    
38.     return 0;
    
39. }

复制代码

输入输出 :

1. 5
   
2. 8 W
   
3. 11 S
   
4. 3 W
   
5. 10 W
   
6. 5 S

复制代码

1. 7

复制代码

解释 :

1. FJ对位置从3到10的牛进行拍照，这个区间有3个白色牛和1个斑点牛，他可以把一个白色牛变成斑点牛，这样两种牛的数量就一样多了。
   
2. 
   
3. 对于30%的数据，n的范围[1,500];
   
4. 
   
5. 对于50%的数据，n的范围[1,5000];
   
6. 
   
7. 对于100%的数据，n的范围[1,100000];
   
8. 
   
9. 每头牛的位置范围[0,10^9];

复制代码

谢谢回答

柿子饼同学

求求了 , 回答给渔币