10.31T3 其他算法思想

T1 蚂蚁移动

（move.cpp/c）

【问题描述】

有一根尺子，长度L<=200000，在上面有N（N <= 70000，N < L）只蚂蚁，且没有两只蚂蚁初始位置相同。每只蚂蚁有一个初始方向（左或者右），且它们会爬行，速度都是每秒一个长度单位。当它们碰到另外一个蚂蚁或者尺子的边缘时，它们会立即改变移动的方向（即反向）。
　　给定尺子的长度，蚂蚁的只数，以及所有蚂蚁初始的位置和方向。要你求第T秒时每只蚂蚁的位置(1<=T<=1000000)。

【输入格式】

第一行两个整数L和T。
　第二行一个整数N，表示蚂蚁的只数。
　接下来的每行由两部分组成。第一部分是一个整数，表示该蚂蚁的初始位置。第二部分是一个字母，表示初始方向：D表示向右，L表示向左。两部分中间空格。

【输出格式】

N个整数，表示每只蚂蚁的最终位置。无需按照蚂蚁的原先编号输出，只要按照最终位置坐标递增（非降）的顺序输出坐标即可。

【样例输入】

5 5
2
2 D
4 L
【样例输出】

1 3

两只蚂蚁相碰等于穿过，就完了

code：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 int a[80000],tot;
 7 int main() {
 8     int L,T;
 9     cin>>L>>T;
10     int n;
11     cin>>n; 
12     T%=2*L;
13     for(int i=1; i<=n; i++) {
14         int pos;
15         char d;
16         cin>>pos>>d;
17         if(d=='L') {
18             a[++tot]=abs(pos-T);
19             if(a[tot]>L)a[tot]-=2*(a[tot]-L);
20         } else {
21             a[++tot]=pos+T;
22             if(a[tot]>L)a[tot]-=2*(a[tot]-L);
23             if(a[tot]<0)a[tot]=-a[tot];
24         }
25     }
26     sort(a+1,a+tot+1);
27     for(int i=1;i<=tot;i++)cout<<a[i]<<" ";
28     return 0;
29 }

over