[BZOJ1637]&&[Usaco2007 Mar]Balanced Lineup

2014-06-20
竞赛题解 / 模拟
BZOJUSACO

描述 Description

Farmer John 决定给他的奶牛们照一张合影，他让 N (1 ≤ N ≤ 50,000) 头奶牛站成一条直线，每头牛都有它的坐标 (范围: 0..1,000,000,000) 和种族(0 或 1)。 一直以来 Farmer John 总是喜欢做一些非凡的事，当然这次照相也不例外。他只给一部分牛照相，并且这一组牛的阵容必须是“平衡的”。平衡的阵容，指的是在一组牛中，种族 0 和种族 1 的牛的数量相等。 请算出最广阔的区间，使这个区间内的牛阵容平衡。区间的大小为区间内最右边的牛的坐标减去最做边的牛的坐标。 输入中，每个种族至少有一头牛，没有两头牛的坐标相同。

输入格式 InputFormat

行 1: 一个整数: N.

行 2..N + 1: 每行两个整数，为种族 ID 和 x 坐标。

输出格式 OutputFormat

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

样例输入 SampleInput

20
1 4525
0 13563
0 15445
0 16963
0 3883
1 1368
1 6852
0 5395
0 19480
1 2032
1 12166
1 7755
1 18458
0 10086
1 11968
1 9629
0 14354
1 17423
1 8562
1 496

样例输出 SampleOutput

13080

来源 Source

Silver

BZOJ 1637

代码 Code

将题目中种类 0 换成 - 1，这问题转换为求和为 0 的区间的最大长度。用 sum[i]表示前缀和，则当 sum[b]-sum[a]=0 时区间 [a+1,b] 为平衡的. 用 first[sum[i]]表示最少前几头牛的种类的和可以达到 sum[i]，则仅需遍历区间右端点更新答案即可。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define f(i) first[i+100000]
const int inf=0x7fffffff/27.11;
struct cow
{
    int id,x;
    bool operator < (const cow &temp) const
    {
        return temp.x>x;
    }
}a[50005];
int sum[50005];
int first[150005];
int i,j,t,n,m,l,r,k,z,y,x;
long long ans;
inline int read()
{
    int x=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int main()
{
    n=read();
    for (i=1;i<=n;i++) a[i].id=(read()==1)?1:-1,a[i].x=read();
    sort(a+1,a+n+1);
    ans=-inf;
    for (i=-50000;i<=50000;i++) f(i)=inf;
    for (i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].id,f(sum[i])=min(f(sum[i]),i);
    for (i=1;i<=n;i++)
    {
        if (f(sum[i])>=i) continue;
        ans=max(ans,(long long)a[i].x-a[f(sum[i])+1].x);
    }
    printf("%lld\n",ans);
    return 0;
}