思维 下标映射 T2 https://vjudge.csgrandeur.cn/problem/UVA-10881
一根长度为 厘米的木棍上有 只蚂蚁,每只蚂蚁要么朝左爬,要么朝右爬,速度为 厘米/秒。当两只蚂蚁相撞时,二者同时掉头(掉头时间忽略不计)。给出每只蚂蚁的初始位置和朝向,计算 秒之后每只蚂蚁的位置。
输入
输入的第一行为数据组数。每组数据的第一行为个正整数;以下 行每行描述一只蚂蚁的初始位置。其中,整数 为蚂蚁距离左端的距离(单位:厘米),字母表示朝向( 表示朝左, 表示朝右)
输出
对于每组数据,输出 行,按输入顺序输出每只蚂蚁的位置和朝向(Turning 表示正在碰撞)。在第 秒之前已经掉下木棍的蚂蚁(正好爬到木棍边缘的不算)输出 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 Turning
6 R
2 Turning
Fell off
Case #2:
3 L
6 R
10 R
思路
思路来自算法入门经典-训练指南
假设你在远处观察这些蚂蚁的运动,会看到什么?一群密密麻麻的小黑点在移动。由于黑点太小,所以当蚂蚁因碰撞而掉头时,看上去和两个点“对穿而过”没有任何区别,换句话说,如果把蚂蚁看成是没有区别的小点,那么只需独立计算出每只蚂蚁在T时刻的位置即可。
比如,有3只蚂蚁,蚂蚁1=(1,R),蚂蚁2=(3,L),蚂蚁3=(4,L),则两秒钟之后,3只蚂蚁分别为(3,R)、(1,L)和(2,L)。
若求的是整体上的结果, 则直接这样处理就行, 不需要考虑掉头问题, 但这里需要关心每个蚂蚁的位置, 而若 蚂蚁1 = (1, R), 则一定存在一只蚂蚁在 (3, R) 的状态, 只不过这只蚂蚁不一定是蚂蚁1。换句话说, 我们需要搞清楚目标状态中的“谁是谁”。
尝试手动处理一下:
一秒之后:
两秒之后:
可以发现, 无论经过多长时间, 任意次碰撞, 蚂蚁1始终会在 蚂蚁2前面, 蚂蚁3始终会在蚂蚁2后面, 因为无法越过一只蚂蚁。
故可以考虑先忽略所有个体之间的碰撞, 对初始位置排序后, 按顺序处理出 秒后所有单位的位置, 然后再根据原本的初始位置来给新位置一一标记, 就是最终结果。
标记状态时用 -1 表示 L, 0 表示 Turning, 1 表示 R。这样当更新位置时直接 就行。
而 时刻的转向判定则是从排序后的蚂蚁位置从小到大枚举, 若当前蚂蚁和下一个蚂蚁的位置相同, 则说明两个都在转向, 需要都将 state 设为 0。
定义 order 数组, 下标对应蚂蚁的输入顺序编号, 而值对应在实际数轴上的位置, 做一个映射。这样输出时只需要从小到大枚举 order 数组来访问结果数组就行。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
// #define debug
int L, T, n;
int order[N];
struct Ant
{
int pos;
int state;
int id;
bool operator<(const Ant &w) const
{
return pos < w.pos;
}
} a[N];
string s[3] = {"L", "Turning", "R"};
void solve()
{
cin >> L >> T >> n;
for (int i = 0; i < n; i++)
{
char op[2];
cin >> a[i].pos >> op;
if (*op == 'L')
a[i].state = -1;
else
a[i].state = 1;
a[i].id = i;
}
sort(a, a + n);
for (int i = 0; i < n; i++)
{
order[a[i].id] = i;
a[i].pos += T * a[i].state;
}
sort(a, a + n);
for (int i = 0; i < n; i++)
if (a[i].pos == a[i + 1].pos || (i && a[i].pos == a[i - 1].pos))
a[i].state = 0;
for (int i = 0; i < n; i++)
{
int j = order[i];
if (a[j].pos <= L && a[j].pos >= 0)
cout << a[j].pos << " " << s[a[j].state + 1] << endl;
else
cout << "Fell off\n";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T, kase = 1;
cin >> T;
while (T--)
{
cout << "Case #" << kase++ << ":\n";
solve();
cout << "\n";
}
return 0;
}