蚂蚁爬杆问题
告诉你有一个长为L（L<=10000）的木杆，上面有N（N<=1000）个蚂蚁，他们一开始的朝向随机，他们会以一定的速度一直向当前方向走，直到两只蚂蚁相遇，他们会立即掉头（即往相反方向走），计算T秒后蚂蚁的位置
输入的第一行为数组个数，
每组数组第一行为三个正整数，L,T,n，分别表示长度，时间，蚂蚁个数。
L 表示向左，R表示向右
输出格式为n行，输出每个蚂蚁的位置和朝向，如果T秒内已经掉下，输出fell off。
样例输入：
1
1014
1R
5 R
3 L
10 R
输出：
Case：#1
2turing
6 R
2 turing
fell off
分析：首先要知道一个原则，蚂蚁的相对位置不变，比如一开始，在148 三个位置有甲乙丙三个蚂蚁，无论每个蚂蚁的位置如何，朝向如何，在不掉下杆的前提下，无论他们怎么对头，他们的相对位置都是不变的，甲一定在乙前面，乙一定在丙前面，只是可能距离发生了改变，位置发生了改变，另外一个原则是，假设在某时刻两个蚂蚁相对而行，而且运行到某一点，这时候他们会掉头运行，但是其结果，其实和对穿而过是一样的，所以我们可以按照这个原则来很快确定其最后状态，比如一开始为1 R3L，5R，经过两秒后，可以判断其最终态一定是3 R,1 L，7R，省略了复杂的分析过程，直接一步到位，只是，位置是3R的，未必是初始位置是1R的。
基于以上两个原则，我们写出如下代码
#include
#include
#include
using namespace std;
const int max=10000;
typedef struct a
{
int id;
int pos;
intstatus;
}ants;
ants before[max];
ants after[max];
int record[max];
const char information[][10]={{"L"},{"turning"},{"R"}};
//1 代表右转-1代表左转0代表正在转身bool cmp(ants & a,ants & b)
{
return a.pos>time;
while(time--)
{
i=0;
j=1;
cin>>L>>T>>n;
len=n;
while(len--)
{
before[i].id=i;
after[i].id=0;
cin>>before[i].pos;
cin>>c_status;
if(c_status=='L')
{
before[i].status=-1;
after[i].status=-1;
}
else if(c_status=='R')
{
before[i].status=1;
after[i].status=1;
}
after[i].pos=before[i].pos+before[i].status*T;
i++;
}
sort(before,before+n,cmp);
sort(after,after+n,cmp);
for(i=0;
i10)
cout<<"Fell off"<
【蚂蚁爬杆问题】
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- parallels|parallels desktop 解决网络初始化失败问题
- jhipster|jhipster 升级无效问题
- “精神病患者”的角度问题
- 解决SpringBoot引用别的模块无法注入的问题
- Hive常见问题汇总
- 姚老师互动问答会|姚老师互动问答会 # 问题001（如何更有智慧的和身边人分享金刚智慧（））
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- 【教育故事】|【教育故事】 一个“问题学生”的蜕变
- 蓝桥杯试题
- 记录iOS生成分享图片的一些问题，根据UIView生成固定尺寸的分享图片