1637: [Usaco2007 Mar]Balanced Lineup

1637: [Usaco2007 Mar]Balanced Lineup

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 393  Solved: 263

[Submit][Status]

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

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

HINT

Source

Silver

 题解:这个嘛,虽然一次性AC了,但是还是有好多的波折——一开始想了半天才有了思路,然后写写写写写,然后中途硬是被打断干别的,然后回来啥都忘了,然后重新瞎折腾代码越改越乱心里越来越烦,然后最后看样子似乎有模有样了,然后Accept,然后没有然后了(想到兴头上被打断思路简直要命啊有木有)。。。好了,说思路——先按照各个牛的位置排个序,然后假如种族为0记-1,1记1,则问题转化为了求最长的和为0的区间,接下来就好办了——记录下同一前缀和的最早出现时间和最晚出现时间,然后找最大时间差即可。。。

var
   i,j,k,l,m,n:longint;
   a,b,c,f:array[0..100000] of longint;
   d,e:array[-60000..60000] of longint;
procedure swap(var x,y:longint);
          var z:longint;
          begin
               z:=x;x:=y;y:=z;
          end;
procedure sort(l,r:longint);
          var i,j,x,y:longint;
          begin
               i:=l;j:=r;
               x:=a[(l+r) div 2];
               repeat
                     while a[i]<x do inc(i);
                     while a[j]>x do dec(j);
                     if i<=j then
                        begin
                             swap(a[i],a[j]);
                             swap(b[i],b[j]);
                             inc(i);dec(j);
                        end;
               until i>j;
               if l<j then sort(l,j);
               if i<r then sort(i,r);
          end;
begin
     readln(n);
     for i:=1 to n do
         begin
              readln(b[i],a[i]);
              if b[i]=0 then b[i]:=-1;
         end;
     sort(1,n);
     c[0]:=0;
     for i:=1 to n do
         c[i]:=c[i-1]+b[i];
     fillchar(d,sizeof(d),-1);
     fillchar(e,sizeof(e),-1);
     for i:=0 to n do
         begin
              if (d[c[i]]=-1) then d[c[i]]:=i;
              e[c[i]]:=i;
         end;
     l:=0;
     for i:=-50000 to 50000 do
         begin
              if e[i]<=d[i] then continue;
              if (a[e[i]]-a[d[i]+1])>l then l:=a[e[i]]-a[d[i]+1];
         end;
     writeln(l);
end.
                          

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 1728 逃离迷宫(DFS经典题,比赛手残写废题)

逃离迷宫 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

3397
来自专栏HansBug's Lab

1627: [Usaco2007 Dec]穿越泥地

1627: [Usaco2007 Dec]穿越泥地 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 504  So...

2617
来自专栏WOLFRAM

九宫格数独游戏

2178
来自专栏专注数据中心高性能网络技术研发

[LeetCode]Math主题系列{第7,9,13,273题}

1.内容介绍 本篇文章记录在leetcode中Math主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结果,...

3487
来自专栏小樱的经验随笔

2017广东工业大学程序设计竞赛决赛 题解&源码(A,数学解方程,B,贪心博弈,C,递归,D,水,E,贪心,面试题,F,贪心,枚举,LCA,G,dp,记忆化搜索,H,思维题)

心得: 这比赛真的是不要不要的,pending了一下午,也不知道对错,直接做过去就是了,也没有管太多! Problem A: 两只老虎 Description ...

3156
来自专栏ml

HDUOJ----1181 变形课

变形课 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java...

3146
来自专栏算法修养

浙江工业大学校赛 XiaoWei的战斗力

XiaoWei的战斗力 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

3308
来自专栏北京马哥教育

用Python分析苹果公司股价数据

专栏地址:https://zhuanlan.zhihu.com/c_147297848

3670
来自专栏新工科课程建设探讨——以能源与动力工程专业为例

3.1.2 使用绘图API绘制Contour的思路

A week or so back I wrote about a package I ported/modified to create the Delaun...

770
来自专栏机器学习从入门到成神

一道面试题到卡特兰数及其应用

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1022

扫码关注云+社区

领取腾讯云代金券