第二届ACM趣味程序设计竞赛 过去也快1个月了 一直没把没过的题搞过去 有点愧对太阳叔叔。所以特此开篇。

 

一开始想复杂了 那么多碰头 该有多复杂啊 就在那模拟来模拟去 伤脑筋 这次比赛也就这题卡的我伤心。。。 

废话不说 讲思路吧。。

题目要求要知道蚂蚁的名字 和掉下去的先后顺序（等死活该）注意到 两边的蚂蚁总是最先掉下去的 其次是内部的。 

一层一层剥下去 这样思路就简单了

只要判定最外边两只哪知先掉下去 

显然需要先排序 

用结构体

struct

Ant{

char

name[

11

];

int

pos;

}ant[

100

];

表示蚂蚁;按pos排序;

#include

<

iostream

>

#include

<

cstdio

>

#include

<

algorithm

>

/*

*

* 1365.ant.

*

* Copyright (C) 2011 luxury2664@gmail.com

*/

using

namespace

std;

struct

Ant{

char

name[

11

];

int

pos;

}ant[

100

];

struct

Event{

int

drop_time;

char

dir;

}eve[

100

];

bool

ant_cmp(

const

Ant

&

ant1,

const

Ant

&

ant2)

{

return

ant1.pos

<

ant2.pos;

}

bool

eve_cmp(

const

Event

&

eve1,

const

Event

&

eve2)

{

return

eve1.drop_time

<

eve2.drop_time;

}

int

main()

{

int

N, L, T, k

=

1

, i;

char

dir[

2

];

scanf(

"

%d

"

,

&

T);

while

(T

--

) {

printf(

"

Case #%d:\n

"

, k

++

);

scanf(

"

%d%d

"

,

&

N,

&

L);

for

(i

=

0

; i

<

N; i

++

) {

scanf(

"

%s%d%s

"

, ant[i].name,

&

ant[i].pos, dir);

eve[i].dir

=

dir[

0

];

eve[i].drop_time

=

(eve[i].dir

==

'

L

'

)

?

ant[i].pos : L

-

ant[i].pos;

}

sort(ant, ant

+

N, ant_cmp);

//

对蚂蚁按pos排序

sort(eve, eve

+

N, eve_cmp);

//

对event按时间顺序排序

int

l

=

0

, r

=

N

-

1

;

/*

*

* 因为最先掉下去的一定是左边或右边的

* 只要判定左边或右边那一个先下去

* 由两只蚂蚁相遇可推出多只蚂蚁间的时间关系 即even。

*/

for

(i

=

0

; i

<

N; i

++

) {

if

(eve[i].dir

==

'

L

'

){

printf(

"

%d %s\n

"

, eve[i].drop_time, ant[l].name);

l

++

;

}

else

{

printf(

"

%d %s\n

"

, eve[i].drop_time, ant[r].name);

r

--

;

}

}

}

return

0

;

}