P1918 保龄球——题解

解题思路

读取位置时建立“瓶子数到位置编号”的哈希映射。每次询问直接在映射中查找，存在则输出对应位置，不存在输出 0。

复杂度分析

期望时间复杂度 $O(n+Q)$，空间复杂度 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;cin>>n;unordered_map<long long,int> pos;pos.reserve(n*2+10);
    for(int i=1;i<=n;i++){long long x;cin>>x;pos[x]=i;}
    int q;cin>>q;while(q--){long long x;cin>>x;auto it=pos.find(x);cout<<(it==pos.end()?0:it->second)<<'\n';}
    return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int n;cin>>n;unordered_map<long long,int> pos;pos.reserve(n*2+10); for(int i=1;i<=n;i++){long long x;cin>>x;pos[x]=i;} int q;cin>>q;while(q--){long long x;cin>>x;auto it=pos.find(x);cout<<(it==pos.end()?0:it->second)<<'\n';} return 0; }