Easy Problem-map和vector的使用

　　给出一个包含n个整数的数组，你需要回答若干询问。每次询问包含两个整数k和v，输出从左到右第k个v的下标（数组下标，从左右到右编号1~n）。

【输入格式】

　　输入包含多组数据。每组数据第一行为两个整数n和m（1<= n，m <=100000），第二行包含n个不超过10^6的正整数，即待查询的数组。以下m行每行包含两个整数k和v（1<=k<=n，1<=v<=10^6）。输入结束标识为EOF。

【输出格式】

　　对于每个查询，输出查询结果。如果不存在，输出0.

【分析】

　　从查询的角度来看，把输入组织成一个可以“只读结果"的数据结构，例如data[v][k]就是答案。但由于v的范围比较大，这里的data不应是一个数组，而是一个STL的map，也就是说data[v]指map中键v对应的”值“，由于我们要以data[v][k]访问，那么data[v]的”值“应该是一个数组，保存整数v从左到右依次出现的下标（因此第k次出现的下标就是data[v][k]）。

　　另外，不同整数出现的次数可能相差很大，data[v]应是一个变长数组，如vector<int>。

　　代码如下：

#include <cstdio>

#include <iostream>

#include <vector>

#include <map>

using namespace std;

map<int,vector<int> > data;

int main()

{

    int n,m,v,k;

    while(scanf("%d%d",&n,&m) == )

    {

        data.clear();

        for(int i = ; i < n; i++)

        {

            scanf("%d",&v);

            if(!data.count(v)) data[v] = vector<int>();

            data[v].push_back(i+);

        }

        while(m--)

        {

            scanf("%d%d",&k,&v);

            if(!data.count(v) || data[v].size() < k)

                printf("0\n");

            else

                printf("%d\n",data[v][k-]);

        }

    }

    system("pause");

    return ;

}

巴特西

Easy Problem-map和vector的使用

最新文章

热门文章