UVA11991 Easy Problem from Rujia Liu? map+vector的妙用

题目描述

​​PDF​​

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例#1： 复制

8 4 1 3 2 2 4 3 2 1 1 3 2 4 3 2 4 2

输出样例#1： 复制

2 0 7 0

思路来自：

刘汝佳:训练指南P187例题.

题意:

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

分析:

        首先看到本题的询问时是v和k，我想有没有什么数据结构直接用X[v][k]就能解决每个询问的？即X[v]中保存的是v这个值出现过的所有下标。由于X[v]的大小不一定且需要能随机存取(取X[v]中的第k个元素为X[v][k])，所以X[v]应该是一个vector<int>。那么X是什么呢？如果X仅仅是一个数组结构，那么我们需要一个100W大小的X数组(因为v<=100W)，其实v的值并不会覆盖的那么广，所以这里我们用map<int, vector<int> > 来表示X。

        所以这里我们可以定义map<int,vector<int> > data.则每个v值对应一个v出现的所有下标构成的向量。对于每个v和k，我们可以直接通过map[v][k-1]直接输出结果(想想是不是).

代码实现：

#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
using namespace std;
#define N 1100
typedef long long ll;
map<int,vector<int> > m;
int main()
{
    int n,q;
    while(scanf("%d%d",&n,&q)!=-1)
    {
     m.clear();
     for(int i=1;i<=n;i++)
       {
           int x;

        scanf("%d",&x);
        if(!m.count(x))
        {
           m[x]=vector<int>();

           //cout<<x<<" "<<ma[x]<<endl;
        }
         m[x].push_back(i);
        // cout<<x<<" "<<m[x].size()<<endl;
       }
       while(q--)
       {
           int x,y;
           scanf("%d%d",&x,&y);
           if(!m.count(y)||m[y].size()<x)
           {
               printf("0\n");
           }
           else
               printf("%d\n",m[y][x-1]);
       }

    }
    return 0;
}