10007:[2013.10.25]P1.滚土豆(potato.pas/c/cpp)

http://dyssldezx.openjudge.cn/fornoip2013/10007/

描述

MM老师看到大家练习信息学奥赛都很辛苦，由于开发出一款植物大战僵尸游戏，让大家放松一下，植物大战僵尸这款游戏中，有很多mini game，其中滚土豆十分有意思。从棋盘右侧不断出现僵尸向左走，玩家需要从左侧摆放土豆来消灭他们。

我们可以认为棋盘是一个6行，60列的矩阵。僵尸出现的那一秒会站在所在行的最右侧（即第60列），之后每1秒向左移动1步。玩家可以随时在屏幕最左端摆放土豆，这时这一行的僵尸全部被滚过去的土豆瞬间消灭。如果僵尸走到第1列没有被消灭，而再向左走，则游戏宣告失败。

现在有n只僵尸来啦！我们告诉你每只僵尸出现的时间以及在哪一行出现，要求你求出最少用多少只土豆才能消灭所有的僵尸。

输入第一行一个正整数n，表示僵尸数量。
之后n行中，每行两个正整数L和t，分别表示僵尸所在行和僵尸出现的时间。输出一个正整数，最少需要多少个土豆样例输入

样例输出

提示n<=2000，t<=100000，1<=L<=6

第一次弱弱的改了下qSort、、虽然本来也没什么好得意的、、

然后我们认为，每一行是独立的，所以说.....

（当然不是多进程什么的、、、）

把第l行情况存到T[l,Tt[l]]中，Tt[l]最终存放第l行有多少个僵尸

然后就没什么难的了、、

Code:(2013.10.25)

 1 Var
 2   Tt:Array[0..7] of longint;
 3   T:array[0..7,0..2001] of longint;
 4   i,j,n:longint;
 5   xx,Iris:longint;
 6 Procedure qSort(l,r,k:longint);
 7   Var
 8     i,j,Mid,Tmp:longint;
 9   Begin
10     i:=l;
11     j:=r;
12     Mid:=T[k,(l+r) Shr 1];
13     Repeat
14       While T[k,i]>Mid Do Inc(i);
15       While T[k,j]<Mid Do Dec(j);
16       if i<=j Then
17         Begin
18           Tmp:=T[k,i];
19           T[k,i]:=T[k,j];
20           T[k,j]:=Tmp;
21           Inc(i);
22           Dec(j);
23         End;
24     Until i>j;
25     if i<r Then qSort(i,r,k);
26     if l<j Then qSort(l,j,k);
27   End;
28 Begin
29   Read(n);
30   For i:=1 to n do
31     Begin
32       Read(j);
33       Inc(Tt[j]);
34       Read(T[j,Tt[j]]);
35     End;
36   For i:=1 to 6 do
37     if Tt[i]<>0 Then qSort(1,Tt[i],i);
38   For i:=1 to 6 do
39     if Tt[i]<>0 Then
40       Begin
41         xx:=T[i,1];
42         Inc(Iris);
43         For j:=2 to Tt[i] do
44           Begin
45             if xx-T[i,j]>=60 Then
46               Begin
47                 xx:=T[i,j];
48                 Inc(Iris);
49               End;
50           End;
51       End;
52   Writeln(Iris);
53 End.
54 (*)CopyRight Catch-22.s.Iris 2013.10.25(*)

这里还有一个不知道是去年还是前年写的代码、、

空间稍微省了一点儿，但是个人觉得没上面那个清晰、、

 1 var
 2   i,n,ans:longint;
 3   time,l:array[1..2000] of longint;
 4   max:array[1..6] of longint;
 5 procedure Qs(a,r:longint);
 6   var
 7     i,j,mid,tmp:longint;
 8   begin
 9     i:=a;
10     j:=r;
11     mid:=Time[random(r-a+1)+a];
12     repeat
13      while Time[i]<mid do i:=i+1;
14      while mid<Time[j] do j:=j-1;
15      if i<=j then
16        begin
17          tmp:=Time[i];
18          Time[i]:=Time[j];
19          Time[j]:=tmp;
20          Tmp:=l[i];
21          l[i]:=l[j];
22          l[j]:=tmp;
23          i:=i+1;
24          j:=j-1;
25        end;
26     until i>j;
27     if a<j then Qs(a,j);
28     if i<r then Qs(i,r);
29 end;
30 begin
31   randomize;//新添加,由此知或许是前年写的、、、
32   readln(n);
33   for i:=1 to n do
34     readln(l[i],time[i]);
35   Qs(1,n);
36   For i:=1 to 6 do
37       Max[i]:=0;
38   ans:=0;
39   for i:=1 to n do
40       if time[i]>max[l[i]] then
41         begin
42           max[l[i]]:=time[i]+59;
43           inc(ans);
44         end;
45   writeln(ans);
46 end.