2014-01-11

UVa 11991 Easy Problem from Rujia Liu? ——(STL map)

STL的应用题目：

题目大意：

给出一个数组，找到其中第n个给定的数值，输出它从1开始的下标。

Input

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

第一行是两个整数n，m。表示数组有n个元素，下一行给出了这个数组。
接下来的m行每行表示一个查询，包含两个整数k和v。

Output

2
0
7
0

任务是找出数组中第k个v值的下标（1-based）

这题不用常规思路，而是考虑使用STL的map。

将数组的数字作为map的下标，将这个数在数组中第几次出现作为值记录下来。因为一个数会出现多次，所以考虑采用vector容器，将这些值保存在vector中。

这样本题使用STL容器map<int, vector<int>> Array。

在查询的时候，只需要查询Array[v][k-1]，然后把这个值输出就可以了。

但是由于存在找不到的情况，所以换用at()方法。at方法在越界的时候会抛出out_of_range异常，我们只要接收这个异常，然后输出0即可。

下面是AC代码：

#include <iostream> 
#include <stdexcept> 
#include <vector> 
#include <map> 
using namespace std; 

map<int, vector<int>> x; 
int main(int agrc, char *agrv[]) { 

    int n,m,k,i,v; 
    while(cin>>n>>m) { 
        x.clear(); 
        for(i=1;i<=n;i++) { 
            cin>>k; 
            x[k].push_back(i); 
        } 
        for(i=1;i<=m;i++){ 
            cin>>k>>v; 
            try{ 
                cout<<x[v].at(k-1)<<endl; 
            }catch(out_of_range &exc){ 
                cout<<0<<endl; 
            } 
        } 
    } 
} 

PS out_of_range定义在stdexcept头文件中，我曾经因为未包含此头文件结果CE掉的奇怪错误。

main