奶牛拍照

柿子饼同学

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

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define M 100005
int n;
struct ss{
    int pos,f;
}A[M];
int last[M<<1];
bool cmp(ss a,ss b){
    return a.pos<b.pos;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        char a[5];
        scanf("%d %s",&A[i].pos,a);
        A[i].f= a[0]=='S'?1:-1;//可以把 'W' into  'S' 即-1变成+1  多了2 故last[i]=min(last[i],last[i+2]) 
    }
    sort(A+1,A+1+n,cmp); // 下面就不知道什么意思了 , 求解
    memset(last,127,sizeof(last));
    int sum=n;
    last[sum]=A[1].pos;
    for(int i=1;i<n;i++){
        sum+=A[i].f;
        last[sum]=min(last[sum],A[i+1].pos);
    }
    for(int i=n<<1;i>=0;--i)last[i]=min(last[i],last[i+2]);
    sum=n;
    int ans=0;
    for(int i=1;i<=n;i++){
        sum+=A[i].f;
        ans=max(ans,A[i].pos-last[sum]);
    }
    printf("%d\n",ans);
    return 0;
}

输入输出 :

5
8 W 
11 S 
3 W 
10 W 
5 S

7

解释 :

FJ对位置从3到10的牛进行拍照，这个区间有3个白色牛和1个斑点牛，他可以把一个白色牛变成斑点牛，这样两种牛的数量就一样多了。

对于30%的数据，n的范围[1,500];

对于50%的数据，n的范围[1,5000];

对于100%的数据，n的范围[1,100000];

每头牛的位置范围[0,10^9];

谢谢回答

柿子饼同学

求求了 , 回答给渔币