TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4872
  • 题目
  • P4872平衡的队列
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,64m
    问题描述

    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: 一个整数,阵容平衡的最大的区间的大小。

    样例输入 1

    7
    0 11
    1 10
    1 25
    1 12
    1 4
    0 13
    1 22

    样例输出 1

    11

    样例输入 2

    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

    样例输出 2

    13080

    提示

    输入1说明 


    有7头牛,像这样在数轴上。 



    输出说明 


    牛 #1 (at 11), #4 (at 12), #6 (at 13), #7 (at 22) 组成一个平衡的最大的区间,大小为 22-11=11 个单位长度。 

     

    对于30%的数据:1<=N<=1000
    对于100%的数据:1<=N<=50000


    来源  bzoj 1637