【蓝桥杯】map和vector的简单练习

一.题目描述

二.问题分析

使用嵌套的容器 时间复杂度为O(NlogN)，O(logN)是map查找的时间复杂度。

#include <iostream>
#include <map>
#include <vector>
using namespace std;

const int N=1e5+10;
int n,m;
map <int,vector<int> > s;


int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        s[a].push_back(i+1);
    }
    while(m--){
        int x,y;
        cin>>x>>y;
        if(s.count(y)==0||s[y].size()<x){
            cout<<'\n';
        }
        else{
            cout<<s[y][x-1];
        }
    }
    
    return 0;
}