本文主要是介绍BZOJ 1637: Balanced Lineup 巧妙变换，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
Farmer John 决定给他的奶牛们照一张合影，他让 N (1 ≤ N ≤ 50,000) 头奶牛站成一条直线，每头牛都有它的
坐标(范围: 0..1,000,000,000)和种族(0或1)。 一直以来 Farmer John 总是喜欢做一些非凡的事，当然这次照相
也不例外。他只给一部分牛照相，并且这一组牛的阵容必须是“平衡的”。平衡的阵容，指的是在一组牛中，种族
0和种族1的牛的数量相等。 请算出最广阔的区间，使这个区间内的牛阵容平衡。区间的大小为区间内最右边的牛
的坐标减去最做边的牛的坐标。 输入中，每个种族至少有一头牛，没有两头牛的坐标相同。
Input
行 1: 一个整数: N 行 2..N + 1: 每行两个整数，为种族 ID 和 x 坐标。
Output
行 1: 一个整数，阵容平衡的最大的区间的大小
这道题可以说是非常巧妙了。
0和1的个数非常难统计，可是如果我们要两个数量相等的话，如果把0看作-1，那么如果一个区间和为0，那么它0和1的个数就相等了。
由于数据的位置是混乱的，我们先记得要坐标进行排序。
接着，用一种类似前缀和的思想，从1到n进行枚举。如果现在这个和在之前没出现过，那么我们就把这个和的位置记录下来，注意这里要存成下一个的坐标，从前缀和的角度出发，如果这里直接有再次出现的减这一位的话，会多剪掉这一位的0或1导致答案错误。所以在后面，如果这个sum值再次出现，那么就可以直接用现在的位置减去之前记录的位置来更新答案了，由于我们希望的肯定是最大的区间，所以这个记录的位置只需要存第一次出现的即可，不用更新。
下附AC代码。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 50005
using namespace std;
int n;
struct nod
{int v,pos;
}a[maxn];
bool operator<(nod a,nod b)
{return a.pos<b.pos;
}
int vis[maxn+maxn];
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&a[i].v,&a[i].pos);if(a[i].v==0)a[i].v=-1;}sort(a+1,a+1+n);int sum=0;int ans=0;for(int i=1;i<=n;i++){sum+=a[i].v;if(vis[sum]==0) vis[sum]=a[i+1].pos;else ans=max(ans,a[i].pos-vis[sum]); }printf("%d\n",ans);
}
这篇关于BZOJ 1637: Balanced Lineup 巧妙变换的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
