思维 下标映射 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。换句话说, 我们需要搞清楚目标状态中的“谁是谁”。

尝试手动处理一下:image.png 一秒之后:image.png 两秒之后:image.png 可以发现, 无论经过多长时间, 任意次碰撞, 蚂蚁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;
}