描述 Description
FJ’s N cows (2 <= N <= 100,000) are standing at various positions along a long one-dimensional fence. The ith cow is standing at position x_i (an integer in the range 0…1,000,000,000) and is either a plain white cow or a spotted cow. No two cows occupy the same position, and there is at least one white cow. FJ wants to take a photo of a contiguous interval of cows for the county fair, but in fairness to his different cows, he wants to ensure there are equal numbers of white and spotted cows in the photo. FJ wants to determine the maximum size of such a fair photo, where the size of a photo is the difference between the maximum and minimum positions of the cows in the photo. To give himself an even better chance of taking a larger photo, FJ has with him a bucket of paint that he can use to paint spots on an arbitrary subset of his white cows of his choosing, effectively turning them into spotted cows. Please determine the largest size of a fair photo FJ can take, given that FJ has the option of painting some of his white cows (of course, he does not need to paint any of the white cows if he decides this is better).
在 X 的非负轴上有 N 个不在同一位置上的数, 0 或 1. 至少有 1 个 0. 可以先任意把 0 染成 1.
区间长度定义为,[L,R] 中最右和最左的数的差的绝对值. 求一个最长区间, 满足区间中所有数 0 和 1 的个数相同. 输出这个最长区间的长度.
输入格式 InputFormat
Line 1: The integer N.
Lines 2..1+N: Line i+1 contains x_i and either W (for a white cow) or S (for a spotted cow).
输出格式 OutputFormat
Line 1: The maximum size of a fair photo FJ can take, after possibly painting some of his white cows to make them spotted.
样例输入 SampleInput
5
8 W
11 S
3 W
10 W
5 S
样例输出 SampleOutput
7
代码 Code
用 - 1 表示 W、1 表示 S，则当且仅当 区间和为非正数且数量为偶数 时构成一张合理的照片。
排序后将奇数位和偶数位分开考虑，按前缀和维护两个单调递增序列，以当前点为区间右端点时，在另一个序列中二分查找不小于当前点前缀和的最远的左端点，更新答案。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
const int inf=0x7fffffff/27.11;
inline void read(int &x)
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
struct cow
{
int s;
char ch;
bool operator < (const cow& temp) const
{
return s<temp.s;
}
}a[100005];
vector <pair <int,int> > v[2];//Prefix_sum,Number.
int ans,sum;
int main()
{
read(n);
for (i=1;i<=n;i++) scanf("%d %c",&a[i].s,&a[i].ch);
sort(a+1,a+n+1);
ans=sum=0;
for (i=1;i<=n;i++)
{
if (v[i&1].empty() || v[i&1].back().first<sum)
{
v[i&1].push_back(make_pair(sum,a[i].s));
}
sum+=(a[i].ch=='W')?-1:1;
j=(i&1)^1;
if (!v[j].empty() && v[j].back().first>=sum)
{
ans=max(ans,a[i].s-lower_bound(v[j].begin(),v[j].end(),make_pair(sum,-inf))->second);
}
}
printf("%d\n",ans);
return 0;
}