本文正體字版由OpenCC轉換

(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