1637: [Usaco2007 Mar]Balanced Lineup
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 393 Solved: 263[][]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: 一个整数，阵容平衡的最大的区间的大小。
Sample Input
7 0 11 1 10 1 25 1 12 1 4 0 13 1 22
Sample Output
11 输入说明 有7头牛，像这样在数轴上。 1 1 0 1 0 1 1 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 输出说明 牛 #1 (at 11), #4 (at 12), #6 (at 13), #7 (at 22) 组成一个平衡的最大的区间，大小为 22-11=11 个单位长度。 <-------- 平衡的 --------> 1 1 0 1 0 1 1 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
HINT
Source
题解：这个嘛，虽然一次性AC了，但是还是有好多的波折——一开始想了半天才有了思路，然后写写写写写，然后中途硬是被打断干别的，然后回来啥都忘了，然后重新瞎折腾代码越改越乱心里越来越烦，然后最后看样子似乎有模有样了，然后Accept，然后没有然后了（想到兴头上被打断思路简直要命啊有木有）。。。好了，说思路——先按照各个牛的位置排个序，然后假如种族为0记-1，1记1，则问题转化为了求最长的和为0的区间，接下来就好办了——记录下同一前缀和的最早出现时间和最晚出现时间，然后找最大时间差即可。。。
var i,j,k,l,m,n:longint; a,b,c,f:array[0..100000] of longint; d,e:array[-60000..60000] of longint;procedure swap(var x,y:longint); var z:longint; begin z:=x;x:=y;y:=z; end;procedure sort(l,r:longint); var i,j,x,y:longint; begin i:=l;j:=r; x:=a[(l+r) div 2]; repeat while a[i]x do dec(j); if i<=j then begin swap(a[i],a[j]); swap(b[i],b[j]); inc(i);dec(j); end; until i>j; if l l then l:=a[e[i]]-a[d[i]+1]; end; writeln(l);end.