UVA11991线性查询

【题目描述】：给出一个包含n个整数的数组，你要回答若干次询问。每次询问两个整数k和v，输出从左到右第k个v的小标（从左到右是1....n）

【算法分析】：Map和vector的使用

详细方法见代码，注意map的使用，这道题在UVA10635王子和公主中可以有新的应用。

【完整代码】:

 1 #include<iostream>
 2 
 3 #include<stdio.h>
 4 
 5 #include<string.h>
 6 
 7 #include<algorithm>
 8 
 9 #include<stdlib.h>
10 
11 #include<math.h>
12 
13 #include<queue>
14 
15 #include<vector>
16 
17 #include<map>
18 
19 #define MAXN 100000+5
20 
21 #define MAXM 20000+5
22 
23 #define oo 9556531
24 
25 #define eps 0.000001
26 
27 #define PI acos(-1.0)//这个精确度高一些
28 
29 #define REP1(i,n) for(int i=0;i<=(n);i++)
30 
31 #define REP2(i,n) for(int i=1;i<=(n);i++)
32 
33 using namespace std;
34 
35  
36 
37 map<int ,vector<int> >Map;//后面的>不要连写
38 
39  
40 
41 int n,m;
42 
43 int main()
44 
45 {
46 
47 //    freopen("in","rb",stdin);
48 
49 //    freopen("out","wb",stdout);
50 
51     while(cin>>n>>m)
52 
53     {
54 
55         Map.clear();
56 
57         for(int i=1;i<=n;i++)
58 
59         {
60 
61             int k;
62 
63             cin>>k;
64 
65             if (!Map.count(k))//没查找到关键字
66 
67             Map[k]=vector<int>();
68 
69             Map[k].push_back(i);
70 
71         }
72 
73         for(;m;m--)
74 
75         {
76 
77             int x,p;
78 
79             cin>>p>>x;
80 
81             if(!Map.count(x) || Map[x].size() < p) cout<<"0"<<endl;
82 
83             else cout<<Map[x][p-1]<<endl;//注意存储个数
84 
85         }
86 
87     }
88 
89     return 0;
90 
91  
92 
93 }

【关键词】：vector和map组合