UVA 10881 - Piotr's Ants【模拟+思维】

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1822

题意:有很多只蚂蚁在一条直线上,每个蚂蚁移动速度都是1,并且有一个初始方向。并且当相邻两个蚂蚁相撞时转向。现在问t时间后各个蚂蚁的位置。

解法:这题的一个致命技巧就是把两只蚂蚁的相撞看作是两只蚂蚁交换穿过对方并且交换蚂蚁的编号。这个是很好理解的,类似于物理的完全弹性碰撞。又由于任何两只蚂蚁的相对位置在这种转弯的情况下不会改变相对位置,因此我们只要视作所有蚂蚁没有蚂蚁的行动。最后根据位置关系对应到原始的位置关系。最后再做位置判断的时候查看是否超出坐标之外即可。

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=10000+5;
 4 struct Ant
 5 {
 6     int id;//顺序
 7     int p;//位置
 8     int d;//转向,-1表示左,0表示碰撞中,1表示右
 9     bool operator <(const Ant& a)const
10     {
11         return p<a.p;
12     }
13 }before[maxn],after[maxn];
14 const char dirName[][10]={"L","Turning","R"};
15 int order[maxn];//输入的第i只蚂蚁是终态中的左数第order[i]只蚂蚁
16 int main()
17 {
18     int K;
19     scanf("%d",&K);
20     for(int kase=1;kase<=K;kase++)
21     {
22         int L,T,n;
23         scanf("%d%d%d",&L,&T,&n);
24         for(int i=0;i<n;i++)
25         {
26             int p,d;
27             char c;
28             scanf("%d %c",&p,&c);
29             d=(c=='L'?-1:1);
30             before[i]=(Ant){i,p,d};
31             after[i]=(Ant){0,p+T*d,d};//所有的蚂蚁相撞后可以看做对穿而过,这里的id是未知的
32         }
33         printf("Case #%d:\n",kase);
34         //计算order数组
35         sort(before,before+n);
36         for(int i=0;i<n;i++)//最巧妙的地方在这里,第一次从左到右所有的蚂蚁的相对位置没有变化
37             order[before[i].id]=i;
38         //计算终态
39         sort(after,after+n);
40         for(int i=0;i<n-1;i++)//修改碰撞中的蚂蚁的方向
41             if(after[i].p==after[i+1].p)
42                 after[i].d=after[i+1].d=0;
43         //输出结果
44         for(int i=0;i<n;i++)
45         {
46             int a=order[i];
47             if(after[a].p<0||after[a].p>L)
48                 printf("Fell off\n");
49             else printf("%d %s\n",after[a].p, dirName[after[a].d+1]);
50         }
51         printf("\n");
52     }
53     return 0;
54 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏calmound

匈牙利算法

今天学习了下匈牙利算法,发现这个早在几个月前学过的知识已经忘记的一干二净了,记得当初学习的时候只是看书,看论文,现在要好好的总结下,防止以后再次忘记。 此次总结...

49770
来自专栏程序员的知识天地

一个开发十年的程序员论:学习Python最正确的步骤(0基础必备)

首先,学习Python编程技术,自学或者参加培训学习都适用,每个人都有自己的学习方式和方法。

11320
来自专栏程序员互动联盟

【答疑释惑第六讲】编程找工作对大学要求高吗?

疑惑一 编程找工作对大学要求高吗? 很多人一边学着编程一边心里有个疑问就是这行出来找工作对大学要求高吗?这个问题平心而论要看情况的。一般的BAT这样的大公司对于...

33850
来自专栏老九学堂

第一次Java串讲

Java基础的知识点结构 “目无全牛 游刃有余” ? 2阶段复习巩固 老九学堂学Java微视频到此已经录制三讲了,我们计划是每二周做一次知识点的串讲,目的是帮...

30580
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day02-代码题

Java基础-day02-代码题 1.打印水果报价单-案例详情 ? 在控制台打印如下的信息: * ----------------购买的水果信息---...

29040
来自专栏诸葛青云的专栏

系统学习C语言方法大全

很多人对学习C语言感到无从下手,经常问我同一个问题:究竟怎样学习C语言?我是一个高级编程师,已经开发了很多年的程序,和很多刚刚起步的人一样,学习的第一个计算机语...

17200
来自专栏java工会

关于逻辑、数学和编程的深层次思考

众所周知,编程离不开数学和逻辑。诚然,很多程序员数学能力并不强,也没有系统的逻辑能力。但是,他们在无意识中,日常工作中,有意无意的就在使用逻辑和数学,并将它们运...

10520
来自专栏技术总结

iOS之DBL_EPSILON,FLT_EPSILON,FLT_MIN和FLT_MAX

34660
来自专栏LeetCode

<dp> 0--1背包问题

有n 个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?

12900
来自专栏Albert陈凯

Scala学习路线

这是一篇为公司内部”scala热情workshop”活动准备的文章,面向Scala初学者,目的在于帮助大家能尽早就建立起对Scala的整体认识,少走弯路。当然由...

64050

扫码关注云+社区

领取腾讯云代金券