题解：P14736 [ICPC 2021 Seoul R] Find the House

· · 题解

Find the House 题解

问题简述

给定起始位置和 n 个三元组 (i, j, k)，表示在位置 i 时，按方向 j 移动距离 k。每个三元组只用一次，求最终位置。

思路与步骤

模拟解决即可.

首先将每个位置 i 作为键映射到对应的移动指令 (j, k) 存入 unordered_map（哈希表比普通 map 速度更快）。

接着从给定的起始位置 pos 开始循环执行：每次查找当前位置在哈希表中对应的指令，获取后就删除该条目（确保每个指令仅使用一次），然后按照方向更新位置，重复此过程直到哈希表为空，此时 pos 的值即为最终所求的位置。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<char,int> PCI;// 先宏定义便于下面的书写

void solve()
{
    int n;
    cin>>n;
    unordered_map<int,PCI> mp;// 使用哈希表存储每个位置 i 对应的方向与距离对 (j, k)
    for(int i=0;i<n;i++){
        int ii,k;
        char j;
        cin>>ii>>j>>k;
        mp[ii]={j,k};
    }
    int pos;
    cin>>pos;
    // 模拟引用三元组的过程，直到所有三元组都被引用
    while(!mp.empty()){
        auto it=mp.find(pos);
        char dir=it->second.first;
        int k=it->second.second;
        mp.erase(it);// 引用后删除（确保每个只用一次）
        // 根据方向移动位置
        if(dir=='L') pos-=k;
        else pos+=k;
    }
    cout<<pos<<'\n';
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    int _=1;//cin>>_;
    while(_--) solve();
    return 0;
}