【暑假】[实用数据结构]UVa11991 Easy Problem from Rujia Liu?

时间:2021-12-24 10:27:37
UVa11991 Easy Problem from Rujia Liu?

 

 思路:  构造数组data,使满足data[v][k]为第k个v的下标。因为不是每一个整数都会出现因此用到map,又因为每个数出现次数不等可能相差很大,因此用到vector。 

  注意:对于数据的清空与判空不要忘记,而map在调用之前必须有map.count的检查。

代码:

 

 1 #include<cstdio>
2 #include<map>
3 #include<vector>
4 using namespace std;
5
6 int main(){
7 int n,m;
8 map<int,vector<int> > table;
9
10 while(scanf("%d%d",&n,&m)==2) {
11 table.clear();
12 int x;
13 for(int i=1;i<=n;i++) {
14 scanf("%d",&x); //
15 if(!table.count(x)) table[x] = vector<int>(); //map.count()的判断很重要 //vector的初始化
16 table[x].push_back(i);
17 }
18 int k,v;
19 for(int i=0;i<m;i++) {
20 scanf("%d%d",&k,&v);
21 if(!table.count(v) || table[v].size()<k) printf("0\n"); //在调用map之前定要count判断
22 else printf("%d\n",table[v][k-1]); //k-1
23 }
24 }
25 return 0;
26 }