Milking Cows [复制链接]

2.2 PROB Milking Cows

这题目，我浪费了多少时间啊！诶……
看看简单，调试啊……

TASK: milk2
LANG: PASCAL

Compiling...
Compile: OK

Executing...
sending data (milk2) milk2 /home/kolstad/trainweb

Test 1 OK [0.003 secs]
Test 2 OK [0.002 secs]
Test 3 OK [0.003 secs]
Test 4 OK [0.006 secs]
Test 5 OK [0.197 secs]
Test 6 OK [0.003 secs]
Test 7 OK [0.006 secs]
Test 8 OK [0.021 secs]

All tests OK.

Your program ('milk2') produced all correct answers!  This is your
submission #17 for this problem.  Congratulations!

{ ID: oifans1 PROG: milk2 LANG: PASCAL } program t1; var a:array[1..1000000] of smallint; j,stmin,enmax,st,en,temp1,temp0,sure1,sure0:longint; i,n:integer; zt:smallint; procedure hat(st,en:longint); begin case a[st] of 0: a[st]:=3; 5: a[st]:= 1; end; case a[en] of 0 : a[en]:=5; 3 : a[en]:=1; end; end; procedure count(t:smallint); begin if zt=1 then begin if t=1 then inc(temp1,2) else begin inc(temp1); if sure1<temp1 then sure1:=temp1; zt:=0; temp0:=1; end; end else begin if t=0 then inc(temp0,2) else begin inc(temp0); if sure0<temp0 then sure0:=temp0; zt:=1; temp1:=1; end; end; end; begin enmax := 0; stmin := 3000001; sure0:=0; sure1:=0; temp0:=0; temp1:=1; assign(input,'milk2.in'); reset(input); assign(output,'milk2.out'); rewrite(output); zt:=1; read(n); for i:= 1 to n do begin read(st,en); if en>enmax then enmax:=en; if st<stmin then stmin:=st; hat(st,en); for j:= st+1 to en-1 do a[j]:=1; end; for j:= stmin+1 to enmax do count(a[j]); if temp0> sure0 then sure0 := temp0; if temp1> sure1 then sure1 := temp1; writeln(sure1 div 2,' ',sure0 div 2); close(output); end.

我一看到这个题目就想，有机会写线段树了（纯粹是为了学习线段树）以前没有找到这么明显的。但是有一个测试点不对。　不知是不是最后统计的时候错了

C语言，看不懂啊～

思路：这题和NOIP2005普及组的第二题很相似了。先开一个100 0002个空间的一维数组，然后初始化为N，然后一步步读入起始点和结束点，用s和e记录最小起始点和最大终止点。用for语句，把开始点+1（为什么要加一你就自己想想吧！）到结束点的时间段改为Y（如果已经是Y，那么重复写也不要紧啊！），然后最后数最长的一串Y和最长的一串N有多少个就是答案了！



参考源代码：



Executing...
    Test 1: TEST OK [0.008 secs]
    Test 2: TEST OK [0.008 secs]
    Test 3: TEST OK [0.008 secs]
    Test 4: TEST OK [0.012 secs]
    Test 5: TEST OK [0.056 secs]
    Test 6: TEST OK [0.008 secs]
    Test 7: TEST OK [0.008 secs]
    Test 8: TEST OK [0.016 secs]

没办法，用P的一个较优的算法（至少比开1000002数组的优）时间就是没有C/C++快啊。。。
P的编译器不行啊

用HASH，暴简单的
{
ID: wangxuan21
PROG: milk2
LANG: PASCAL
}

var n,i,j,t1,t2,max,min,p,q:longint;
    a:array[1..1000000]of boolean;
begin
assign(input,'milk2.in');
reset(input);
assign(output,'milk2.out');
rewrite(output);
read(n);
max:=0;
min:=maxlongint;
for i:=1 to 1000000 do
    a:=false;
for i:=1 to n do
    begin
    read(t1,t2);
    for j:=t1 to t2-1 do a[j]:=true;
    if max<t2-1 then max:=t2-1;
    if t1<min then min:=t1;
    end;
t1:=0; t2:=0;
p:=0; q:=0;
for i:=min to max do
    begin
    if a=true then
                  begin
                  if t2>q then q:=t2;
                  t2:=0;
                  inc(t1);
                  end;
    if a=false then
                  begin
                  if t1>p then p:=t1;
                  t1:=0;
                  inc(t2);
                  end;
    end;
if t1=0 then if t2>q then q:=t2;
if t2=0 then if t1>p then p:=t1;
writeln(p,' ',q);
close(input);
close(output);
end.

hen hao

{
ID: w1992072
PROG: milk2
LANG: PASCAL
}
PROGRAM milk2;
TYPE
arr=array[1..100000] of longint;
VAR
a1,a2:arr;
n,i,j,l,r,x1,x2:longint;

FUNCTION max(a,b:longint):longint;
begin
max:=a;
if b>a then max:=b;
end;

PROCEDURE qsort(var a:arr;l,r:longint);
var
x,t1,t2,i,j:longint;
begin
i:=l;j:=r;
x:=a;
repeat
  while (a<x) do inc(i);
  while (a[j]>x) do dec(j);
  if (i<=j) then
    begin
    t1:=a;a:=a[j];a[j]:=t1;
    t2:=a2;a2:=a2[j];a2[j]:=t2;
    inc(i);dec(j);
    end;
until i>j;
if (l<j) then qsort(a,l,j);
if (i<r) then qsort(a,i,r);
end;

BEGIN
assign(input, 'milk2.in');
reset(input);
assign(output, 'milk2.out');
rewrite(output);
readln(n);
for i:=1 to n do readln(a1,a2);
qsort(a1,1,n);
l:=a1[1];
r:=a2[1];
for i:=1 to n do
    begin
      if a1<=r then
        r:=max(a2,r)
      else begin
        x1:=max(x1,r-l);
        x2:=max(x2,a1-r);
        l:=a1;
        r:=a2;
      end;
    end;
    x1:=max(x1,r-l);
writeln(x1,' ',x2);
Close(input);
Close(output);
END.