uva10881

思维题
区间内点的移动（形象）保持原有顺序+重新排序后记录初始位置（容易思路不清）+想象等效模型
 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 #include<algorithm>
 5 #define maxn 10000+10
 6 using namespace std;
 7 struct ant
 8 {
 9     int ord;//记录原始位置
10     int f;//-1 : L , 1 : R
11     int p;
12     bool operator < (const ant &aa) const{return p<aa.p;}
13 }b[maxn],a[maxn];
14 char fface[5][10]={"L","Turning","R"};
15 int ford[maxn];//记录按照输入的第i只蚂蚁在排序后的位置
16 int main()
17 {
18     //freopen("out.txt","w",stdout);
19     int ts;
20     scanf("%d",&ts);
21     {
22         for(int cas=1;cas<=ts;cas++)
23         {
24 
25             int l,t,n;
26             scanf("%d%d%d",&l,&t,&n);
27             for(int i=0;i<n;i++)
28             {
29                 char face[5];
30                 int f;//-1:L 1:R
31                 int p;
32                 scanf("%d %s",&p,face);//读取字符必须用字符串，不然需要考虑空格和换行问题！！！
33                 f=(face[0]=='L')?-1:1;
34                 b[i]=(ant){i,f,p};//这种以前没有用过
35                 a[i]=(ant){0,f,p+f*t};//爬行后
36             }
37             sort(b,b+n);
38             for(int i=0;i<n;i++)
39             {
40                 ford[b[i].ord]=i;//这个对应方式很巧妙啊，一一对应，就是容易弄混，时间复杂度很低
41             }
42             sort(a,a+n);//爬行后的坐标按照从左到右的顺序排列
43             for (int i=0;i<n-1;i++)
44             {
45                 if (a[i].p==a[i+1].p)
46                 {
47                     a[i].f=0;a[i+1].f=0;
48                 }
49             }//算法虽然简单，但是用处很大，可用于：1、多个数是否相等的判断 2、标记数组连续相等的线段
50             printf("Case #%d:
",cas);
51             for(int i=0;i<n;i++)
52             {
53                 int k=ford[i];//在B中第i号元素应该在A中的序号
54                 if (a[k].p<0 || a[k].p>l)
55                 {
56                     printf("Fell off
");
57                     continue;
58                 }
59                 else
60                 {
61                 printf("%d ",a[k].p);
62                 printf("%s
",fface[a[k].f+1]);//这种方式比if判断方便多了，很精简
63                 }
64             }
65             printf("
");
66         }
67     }
68     return 0;
69 }