题意：给一根长度为L的木头，上面有A只蚂蚁【每只蚂蚁给出了初始行走的方向，向左或向右】。当两只蚂蚁相碰时，两只蚂蚁就朝相反的方向行走~╮(╯▽╰)╭问的是：最后掉下来的蚂蚁用时多少，并且它的初始位置是哪里？【若有两只，就先输出初始位置小的那只】~
这道题跟白书里的那道题十分的像，不过白书问的是：给出时间T，问最后每只蚂蚁的位置是什么~
题目的关键是：
1.当两只蚂蚁相碰的时候，其实就好像是两只蚂蚁穿过了~那么，每输入一只蚂蚁，那么一定存在对应的一只蚂蚁【也可能是自身】符合：若它要掉下来，那么它走的路程就是——若向右，X=L-P；若向左，X=P【X为要走的路程，P为输入的那只蚂蚁的初始坐标，L为木头长度】。由于速度是一格每秒，故最后的那只蚂蚁掉下来的蚂蚁用时T为所有X中最大的~同样，由于把蚂蚁相碰当成对穿而过，就没办法确定终态的蚂蚁是始态的那只蚂蚁了。换句话说：我们剩下就是搞清楚终态的蚂蚁对应的是那只始态的蚂蚁~
2.其次，我们可以注意到蚂蚁的相对位置是始终不变的，因此把所有目标位置从小到大排好序，则从左到右的每个位置对应始态的从左到右的每只蚂蚁。由于原题不一定按从左到右的顺序输入，还需要预处理计算出输入中的第i只蚂蚁的顺序号order[i]。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define Max 100111 struct Ant {
int id; //输入顺序
int p; //输入位置
int d; //输入蚂蚁的方向，-1为向左，1为向右，0为转身中
bool operator < (const Ant& a) const {
return p>a.p;
}
}before[Max],after[Max]; int order[Max]; //输入的第i只蚂蚁是终态中的左数第order[i]只~ int main(){
int A,L;
while(~scanf("%d%d",&L,&A))
{
memset(before,,sizeof(before));
memset(after,,sizeof(after));
int i,j,MM=; //MM为最后的蚂蚁要掉下来的时间
for(i=;i<A;i++)
{
int p,d;
char c;
scanf("%d %c",&p,&c);
d=(c=='L'?-:);
before[i]=(Ant){i,p,d};
after[i]=(Ant){,,d}; //终态的id是未知的
if(d==) //计算出MM的值
MM=max(MM,L-p);
else
MM=max(MM,p-);
}
for(i=;i<A;i++) //计算出经过MM时间后蚂蚁的终态位置
after[i].p=(MM)*after[i].d+before[i].p;
//计算order数组
sort(before,before+A);
for(i=;i<A;i++)
order[before[i].id]=i;
//计算终态
sort(after,after+A);
for(i=;i<A-;i++)
if(after[i].p==after[i+].p) after[i].d=after[i+].d=;
int k=,x[]; //x[]记录的是最后两只蚂蚁的始态，k为最后掉下来的蚂蚁数
memset(x,,sizeof(x));
for(i=;i<A;i++)
{
int a=order[i];
if(after[a].p== || after[a].p==L)
x[k++]=before[a].p;
}
if(k==) printf("The last ant will fall down in %d seconds - started at %d.\n",MM,x[]);
else
{
sort(x,x+);
printf("The last ant will fall down in %d seconds - started at %d and %d.\n",MM,x[],x[]);
}
}
return ;
}
//memory：4224KB time：224ms