- 首页 > it技术 > >
狂奔のC/C++|C/C++每日小练（八）——蚂蚁
蚂蚁
一根长度为L厘米的木棍上有n只蚂蚁，每只蚂蚁要么朝左爬，要么朝右爬，速度为1厘米/秒。当两只蚂蚁相撞时，二者同时掉头（掉头时间忽略不计）。给出每只蚂蚁的初始位置和朝向，计算T秒之后每只蚂蚁的位置。
输入格式：
输入的第一行为数据组数。每组数据的第一行为3个正整数L、T、n（0<=n<=10000）；以下n行每行描述一只蚂蚁的初始位置，其中，整数x为蚂蚁距离木棍左端的距离（单位：厘米），字母表示初始朝向（L表示朝左，R表示朝右）。
输出格式：
对于每组数据，输出n行，按输入顺序输出每只蚂蚁的位置和朝向（Turing表示正在碰撞）。在第T秒之前已经掉下木棍的蚂蚁（正好爬到木棍边缘的不算）输出Fell off。
样例输入：
2
10 1 4
1 R
5 R
3 L
10 R
10 2 3
4 R
5 L
8 R
样例输出：
Case #1:
2 Turing
6 R
2 Turing
Fell off
Case #2:
【狂奔のC/C++|C/C++每日小练（八）——蚂蚁】3 L
6 R
10 R
解：
#include
#include
using namespace std;
const int maxn = 10000+5;
const char dirName[][10] = {"L", "Turing", "R"};
int order[maxn];
//输入的第i只蚂蚁是终态中的左数第order[i]只蚂蚁
struct Ant
{
int id;
//输入顺序
int p;
//位置
int d;
//朝向。-1:左；0:转身中；1：右
bool operator < (const Ant &a) const
{
return p < a.p;
}
}before[maxn], after[maxn];
int main()
{
int K;
scanf("%d", &K);
for(int ki = 1;
ki <= K;
ki++)
{
int L, T, n;
scanf("%d%d%d", &L, &T, &n);
for(int i = 0;
i < n;
i++)
{
int p, d;
char c;
scanf("%d %c", &p, &c);
d = (c=='L') ? -1 : 1;
before[i].id = i;
before[i].p = p;
before[i].d = d;
after[i].id = 0;
after[i].p = p+T*d;
after[i].d = d;
//此处id还是未知的，用0代替
}//计算次序数组
sort(before, before+n);
for(i = 0;
i < n;
i++)
order[before[i].id] = i;
//计算终态，保持原态或其它态
sort(after, after+n);
for(i = 0;
i < n-1;
i++)
if(after[i].p == after[i+1].p) after[i].d = after[i+1].d = 0;
//输出结果
printf("Case #%d:\n", ki);
for(i = 0;
i < n;
i++)
{
int a = order[i];
//恢复输入次序
if(after[a].p < 0 || after[a].p > L) printf("Fell off\n");
else printf("%d %s\n", after[a].p, dirName[after[a].d+1]);
}
printf("\n");
}
return 0;
}
运行结果： 
文章图片
推荐阅读
