CJOJ 2485 UVa 11991 生日礼物 / UVa 11991 Easy Problem from Rujia Liu?

Description

(原题来自刘汝佳《训练指南》Page187,UVa 11991.)

可爱的小F就要过生日啦，为了刷存在感，我们的小F十分诚恳(xian de mei shi)地向女神小E要生日礼物。不过傲娇(2333)的小E当然不会随便答应的啦~为了为难小F，小E就说：

“如果你能做出这道简单题，我就给你礼物；如果做不出来，嘿嘿嘿嘿…” 小F感到一丝杀气…

为了保小命&拿到礼物，信息学渣渣小F只得向你求助，小F能不能拿到梦寐以求的女神的礼物，全靠你了！

给出一个包含n个整数的数组，你需要回答m个询问。 每次询问两个整数k和v，输出从左到右第k个v的下标(数组下标从左到右编号为1~n)。

英文版（原题）： Though Rujia Liu usually sets hard problems for contests (for example, regional contests like Xi'an 2006, Beijing 2007 and Wuhan 2009, or UVa OJ contests like Rujia Liu's Presents 1 and 2), he occasionally sets easy problem (for example, `the Coco-Cola Store' in UVa OJ), to encourage more people to solve his problems :D

Given an array, your task is to find the k-th occurrence (from left to right) of an integer v.To make the problem more difficult (and interesting!),you'll have to answer m such queries.

Input

每组数据第一行为两个整数n和m，第二行包含n个正整数，即待查询的数组。 以下m行每行包含两个整数k和v，意义与题目描述中的相同。 1<=n,m<=100000. 数组中的元素均不超过100000. 1<=k<=n,1<=v<=100000.

Output

对于每个查询，输出查询结果。如果不存在，输出0。

Sample Input

5 3 1 2 3 3 5 1 1 2 5 2 3

Sample Output

1 0 4

Http

CJOJ:http://oj.changjun.com.cn/problem/detail/pid/2485 UVA:https://vjudge.net/problem/UVA-11991

Source

STL

题目大意

有一个n个整数的数组，接下来有m个询问，每个询问有两个整数k,v，输出从左到右第k个v的下标，若不存在则输出0

解决思路

这道题是Vector的运用，令Map[i]表示数字i在数组中出现的位置,从左往右，那么查询的时候就只要输出Map[v][k]即可。 （这么简单的题不需要注释吧）

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<map> #include<vector> using namespace std; int n,m; map<int , vector<int> > Map; int main() { while (cin>>n>>m) { int x; int k,v; Map.clear(); for (int i=1;i<=n;i++) { cin>>x; Map[x].push_back(i); } for (int i=1;i<=m;i++) { cin>>k>>v; //cout<<Map[v].size()<<' '; if (Map[v].size()<k) { cout<<0<<endl; } else cout<<Map[v][k-1]<<endl; } } return 0; }

转载于:https://www.cnblogs.com/SYCstudio/p/7137712.html

相关资源：JAVA上百实例源码以及开源项目