UVA11991 - Easy Problem from Rujia Liu?（数据结构，模拟）

题意:

        给你n个数(n<=10w,但是数值<=100w),现在要你回答m个查询,对于每个查询都是k和v,要求你回答原始数据中第k个v值出现的原始下标,如果不存在输出0.

解法：

我的第一想法是用数组模拟，即d[v][k];但是似乎没有这么大的二维数组，而且也并不知道V到底有多少个，所以用了个向量Vector，本来是不抱任何希望的，没想到A了，果然是水题。。。。

第一次代码：

<span style="font-size:18px;">#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxx=1000001;
vector<int>num[maxx];
vector<int>::iterator it;
int main(){
ios_base::sync_with_stdio(false);
int n,m,a,b,ji;
while(cin>>n>>m)
{
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        num[a].push_back(i);
    }
    while(m--)
    {
        cin>>a>>b;bool flag=false;
    for(it=num[b].begin(),ji=1;it!=num[b].end();ji++,it++)//亏我还是用的迭代器，一个size就能解决的问题。。。。
        if(a==ji){cout<<*it<<endl;flag=true;break;}
        if(!flag)cout<<"0"<<endl;

    }
}
return 0;}</span>

汝佳神的做法是map+vector，虽然我并不知道在这个题目中map和数组有什么区别。。。。。

代码如下：

<span style="font-size:18px;">#include<iostream>
#include<cstring>
#include<map>
#include<vector>
using namespace std;
map<int,vector<int> >ma;
int main(){
int n,m,a,b;
while(cin>>n>>m)
{
    ma.clear();
    for(int i=1;i<=n;i++){
    cin>>a;
    ma[a].push_back(i);
    }
    while(m--)
    {
        cin>>a>>b;
        if(!ma[b].size()||ma[b].size()<a)cout<<"0"<<endl;
        else cout<<ma[b][a-1]<<endl;
    }
}

return 0;}
</span>

看了汝佳神的代码之后，深感自己用迭代器的笨拙，改进第一份如下：

<span style="font-size:18px;">#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxx=1000001;
vector<int>num[maxx];
int main(){
ios_base::sync_with_stdio(false);
int n,m,a,b,ji;
while(cin>>n>>m)
{
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        num[a].push_back(i);
    }
    while(m--)
    {
        cin>>a>>b;
   if(num[b].size()<a)cout<<"0"<<endl;
else cout<<num[b][a-1]<<endl;
    }
}
return 0;}</span>

第三份代码是最快的。。。。毕竟数组存取只有N的时间。。。