题意分析

题目描述了一个一维线性世界上的居民运动模型。关键规则如下：

1. 初始状态：所有居民同时被创建，以相同速度向正（右）或负（左）方向匀速运动
2. 碰撞规则：当两个居民相遇时，他们会瞬间交换运动方向（无时间损耗）
3. 边界规则：当居民到达世界边界（0或L位置）时，会掉落消失
4. 求解目标：确定最后一个掉落的居民及其掉落时间

输入包括：

• 居民数量 N（N < 32000）
• 世界长度 L 和居民速度 V
• 每个居民的初始方向、位置和名字

输出要求：

• 最后掉落的居民名字
• 掉落时间（保留两位小数，13字符宽）

解题思路

关键观察与物理模型转换

1. 碰撞等效原理（核心洞察）：

   • 当两个居民碰撞反向时，可视为他们"穿过"对方继续原方向运动
   • 物理效果等价于居民不改变方向，但名字随碰撞交换
   • 例如：居民A（向右）与B（向左）碰撞后，相当于A带着B的名字向右运动，B带着A的名字向左运动

2. 独立运动模型：

   • 将每个居民看作独立运动（不碰撞）
   • 初始向左的居民最终从0位置掉落，时间 = POS / V
   • 初始向右的居民最终从L位置掉落，时间 = (L - POS) / V
   • 最后一个掉落的居民对应独立运动中最大掉落时间

3. 名字传递规则：

   • 实际最后掉落的居民名字需通过碰撞传递确定
   • 排序后，若第k个居民是最后掉落者：
     • 若初始向右：名字传递到k + 右侧向左居民数量处
     • 若初始向左：名字传递到k - 左侧向右居民数量处

算法步骤

1. 数据预处理：

   • 将向左居民的坐标取负值（-POS），向右居民保持不变
   • 例如：向右POS=3.5 → +3.5；向左POS=3 → -3.0

2. 按绝对位置排序：

   • 按|POS|升序排列（距原点最近到最远）
   • 例如：[-7, -3, 1, 5] → 排序后[1, -3, 5, -7]

3. 计算最大掉落时间：

   • 向左居民：-POS / V（从0掉落）
   • 向右居民：(L - POS) / V（从L掉落）
   • 遍历所有居民，记录最大时间及其索引k

4. 确定最终名字：

   if (方向向右) {
      统计右侧所有向左居民数量cnt
      最终名字 = 排序后[k + cnt]的居民名字
   } else {
      统计左侧所有向右居民数量cnt
      最终名字 = 排序后[k - cnt]的居民名字
   }
   

5. 输出格式化：

   • 时间截断到两位小数（非四舍五入）
   • 结果占13字符宽：printf("%13.2f %s\n", time, name)

时间复杂度

• 排序：O(N log N)
• 最大时间查找：O(N)
• 名字传递统计：O(N)
• 整体复杂度：O(N log N)（满足N<32000）

代码实现

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 32000;

struct Inhabitant {
    char dir;
    double pos;
    string name;
};

bool cmp(const Inhabitant &a, const Inhabitant &b) {
    return abs(a.pos) < abs(b.pos);
}

int main() {
    int n;
    while (cin >> n && n) {
        double L, V;
        cin >> L >> V;
        
        vector<Inhabitant> inhabitants(n);
        for (int i = 0; i < n; i++) {
            cin >> inhabitants[i].dir >> inhabitants[i].pos;
            getline(cin, inhabitants[i].name);
            // 去除名字前多余空格
            inhabitants[i].name.erase(0, inhabitants[i].name.find_first_not_of(' '));
            if (inhabitants[i].dir == 'n' || inhabitants[i].dir == 'N') {
                inhabitants[i].pos = -inhabitants[i].pos;
            }
        }

        // 按绝对位置排序
        sort(inhabitants.begin(), inhabitants.end(), cmp);

        double max_time = -1;
        int k = 0;
        // 计算最大掉落时间
        for (int i = 0; i < n; i++) {
            double t;
            if (inhabitants[i].pos < 0) { // 向左居民
                t = -inhabitants[i].pos / V;
            } else { // 向右居民
                t = (L - inhabitants[i].pos) / V;
            }
            if (t > max_time) {
                max_time = t;
                k = i;
            }
        }

        int cnt = 0;
        // 名字传递统计
        if (inhabitants[k].pos > 0) { // 初始向右
            for (int i = k + 1; i < n; i++) {
                if (inhabitants[i].dir == 'n' || inhabitants[i].dir == 'N') cnt++;
            }
            k += cnt;
        } else { // 初始向左
            for (int i = k - 1; i >= 0; i--) {
                if (inhabitants[i].dir == 'p' || inhabitants[i].dir == 'P') cnt++;
            }
            k -= cnt;
        }

        // 时间截断处理
        double display_time = static_cast<int>(max_time * 100) / 100.0;
        printf("%13.2f %s\n", display_time, inhabitants[k].name.c_str());
    }
    return 0;
}