本文主要是介绍uva - 11991 - Easy Problem from Rujia Liu?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：输入一个长度为n个数组（元素为[1, 1,000,000]之间的正整数），接着输入m个询问（1 <= n, m <= 100,000），第个询问为两个数k, v（1 <= k <= n，1 <= v <= 1,000,000），问数组中第k个v的下标是多少？
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3142
——>>如果每个询问都搜索一次，猜想超时过不了！于是将其弄成一一映射，用data[v][k]存第k个v的下标，询问的时候O(1)的输出，就不会超时喽！用STL中的map与vector来做就好，汝佳牛真的太神啦！谢谢！
#include <iostream>
#include <map>
#include <vector>using namespace std;int main()
{int n, m, i, temp, v;unsigned k;while(cin>>n>>m){map<int, vector<int> > data;for(i = 1; i <= n; i++){cin>>temp;if(!data.count(temp)) //如果不存在键值temp，则返回0data[temp] = vector<int>(); //对键值为temp的键开向量data[temp].push_back(i); //存入下标}for(i = 0; i < m; i++){cin>>k>>v;if(!data.count(v) || k > data[v].size()) //如果不存在键值v，或者是第k个v已经不在向量中的话cout<<0<<endl;elsecout<<data[v][k-1]<<endl; //向量的下标是从0开始的，所以第k个数对应着向量中的下标k-1}}return 0;
}
做第二次：
#include <cstdio>
#include <vector>using namespace std;const int maxn = 1000000 + 10;
vector<int> data[maxn];int main()
{int n, m, i, temp, v;unsigned k;while(scanf("%d%d", &n, &m) == 2){for(i = 0; i < maxn; i++) data[i].clear();for(i = 1; i <= n; i++){scanf("%d", &temp);data[temp].push_back(i); //存入下标}for(i = 0; i < m; i++){scanf("%d%d", &k, &v);if(data[v].empty() || k > data[v].size()) //如果不存在v，或者是第k个v已经不在向量中的话printf("0\n");elseprintf("%d\n", data[v][k-1]); //向量的下标是从0开始的，所以第k个数对应着向量中的下标k-1}}return 0;
}
这篇关于uva - 11991 - Easy Problem from Rujia Liu?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
