(Some by Zqzas)

读入时，直接将种类0换成-1，这样我们就可以把问题转化为求和为0最大的区间。然后根据坐标顺序排序。

O(N^3)的算法: 最基本的算法,枚举起始和结束的位置,然后再用O(N)的时间计算出区间内数字和.显然超时.

O(N^2)的算法: 在上一个算法的基础上进行改进,用sum[i]表示前i个数的数字和,那么从第a+1个数到第b个数的数字和就是sum[b]-sum[a]. sum可以在初始化时算出,这样就可以用O(1)时间算出区间内的数字和.但还是超时.

O(N*LogN)的算法: 在N^2算法的基础上改进,不能暴力地枚举区间.

由于sum[i]的范围是从-50000到50000,那么就可以试图借助hash来提高效率.

观察sum[b]-sum[a]这个式子,可以发现当sum[b]-sum[a]=0时,[a+1,b]区间是平衡的,即sum[b]=sum[a],那么我们就可以枚举b的位置,为了得到更大的区间,要使sum[b]=sum[a]中的a尽量小。

可以用hash[sum[i]]表示最少前几个数字的和可以达到sum[i].另一种表述方式:记sum[j]=sum[i],且使j尽量小(j<=i),那么hash[sum[i]]=j.hash也可以在线性时间内算出。

#include <iostream>
#define MAX 50002
 
using namespace std;
 
typedef struct
{
	int S,V;
}Point;
 
int N,Ans;
int Sum[MAX];
Point P[MAX];
int *Hash;
 
inline int cmp(const void *a ,const void *b)
{
	return ((Point *)a)->S - ((Point *)b)->S;
}
 
int main()
{
	int i,j,L;
	freopen("balance.in","r",stdin);
	freopen("balance.out","w",stdout);
	scanf("%d",&N);
	Hash=(int *)malloc(MAX*2*sizeof(int));
	Hash+=MAX;
	for (i=-50000;i<=50000;i++)
		Hash[i]=0x7FFFFFFF;
	for (i=1;i<=N;i++)
	{
		scanf("%d%d",&P[i].V,&P[i].S);
		if (!P[i].V)
			P[i].V=-1;
	}
	qsort(P+1,N,sizeof(P[0]),cmp);
	for (i=1;i<=N;i++)
	{
		Sum[i]=Sum[i-1]+P[i].V;
		if (i<Hash[Sum[i]])
			Hash[Sum[i]]=i;
	}
	for (i=1;i<=N;i++)
	{
		j=Hash[Sum[i]];
		if (j>=i) continue;
		L=P[i].S-P[j+1].S;
		if (L>Ans)
			Ans=L;
	}
	cout << Ans << endl;
	return 0;
}

<a href="http://www.ruvtex.cn/wiki/USACOMonthly/2007_03_S/Balanced_Lineup/Chinese">平衡的阵容</a>

译 By BYVoid

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
0 11
1 10
1 25
1 12
1 4
0 13
1 22

输出样例

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

上次修改时间 2017-02-03