题目名称	166. [USACO Mar07] 平衡的阵容
输入输出	`balance.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	BYVoid 于2008-10-07加入
开放分组	全部用户
提交状态
分类标签	USACO 散列贪心平衡树
	分享题解

通过：64，提交：158，通过率：40.51%
·	100	0.047 s	1.08 MiB	C++
HouJikan	100	0.052 s	1.08 MiB	C++
jhyjhy	100	0.060 s	4.38 MiB	C++
rewine	100	0.061 s	1.09 MiB	C++
xrq	100	0.063 s	0.97 MiB	C++
MloVtry	100	0.069 s	1.27 MiB	C++
Sky_miner	100	0.071 s	0.89 MiB	C++
再见	100	0.071 s	2.49 MiB	C++
lucifer	100	0.076 s	0.93 MiB	Pascal
qing	100	0.077 s	11.49 MiB	C++

本题关联比赛
20091112练习

关于平衡的阵容的近10条评论(全部评论)
`map`水掉QWQ sssSSSay 2017-10-23 21:22 6楼
说好的不会超时呢，我还打了3个点 open the window 2016-08-17 12:10 5楼
O（n*n）效率竟然过了，评测机还真是给力。 RP++ 2014-10-30 18:02 4楼
回复 @派大大 : 大神贪心算法狂拽炫酷D炸天 · 2014-10-30 18:01 3楼
回复 @phoenix : 以......的名义声明，2楼大神根本不会Pascal。 RP++ 2014-10-30 17:42 2楼
O(nn) 前缀和枚举， O（nlogn）哈希 · 2014-10-30 17:27 1楼

166. [USACO Mar07] 平衡的阵容

★★ 输入文件：balance.in 输出文件：balance.out 简单对比
时间限制：1 s 内存限制：128 MiB

译 By CmYkRgB123

【题目描述】

Farmer John 决定给他的奶牛们照一张合影，他让 N (1 ≤ N ≤ 50,000) 头奶牛站成一条直线，每头牛都有它的坐标(范围: 0..1,000,000,000)和种族(0或1)。

一直以来 Farmer John 总是喜欢做一些非凡的事，当然这次照相也不例外。他只给一部分牛照相，并且这一组牛的阵容必须是“平衡的”。平衡的阵容，指的是在一组牛中，种族0和种族1的牛的数量相等。

请算出最广阔的区间，使这个区间内的牛阵容平衡。区间的大小为区间内最右边的牛的坐标减去最做边的牛的坐标。

【输入格式】

行 1: 一个整数: N
行 2..N + 1: 每行两个整数，为种族 ID 和 x 坐标。
输入中，每个种族至少有一头牛，没有两头牛的坐标相同。

【输出格式】

行 1: 一个整数，阵容平衡的最大的区间的大小。

【输入样例】

【输出样例】

【样例解释】

有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