奶牛拍照
题解看不懂 , 思路大概是把白的看成 -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;
int last;
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;
scanf("%d %s",&A.pos,a);
A.f= a=='S'?1:-1;//可以把 'W' into'S' 即-1变成+1多了2 故last=min(last,last)
}
sort(A+1,A+1+n,cmp); // 下面就不知道什么意思了 , 求解
memset(last,127,sizeof(last));
int sum=n;
last=A.pos;
for(int i=1;i<n;i++){
sum+=A.f;
last=min(last,A.pos);
}
for(int i=n<<1;i>=0;--i)last=min(last,last);
sum=n;
int ans=0;
for(int i=1;i<=n;i++){
sum+=A.f;
ans=max(ans,A.pos-last);
}
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的范围;
对于50%的数据，n的范围;
对于100%的数据，n的范围;
每头牛的位置范围;
谢谢回答{:10_303:} 求求了 , 回答给渔币
页:
[1]