题意:训练指南P187
分析:用vector存id下标,可以用map,也可以离散化用数组存(发现不用离散化也可以)
map
#include <bits/stdc++.h>
using namespace std;
map<int, vector<int> >mp;
int main(void) {
int n, m;
while (scanf ("%d%d", &n, &m) == 2) {
mp.clear ();
for (int a, i=1; i<=n; ++i) {
scanf ("%d", &a);
if (!mp.count (a)) mp[a] = vector<int> ();
mp[a].push_back (i);
}
while (m--) {
int k, v; scanf ("%d%d", &k, &v);
if (!mp.count (v) || mp[v].size () < k) puts ("0");
else printf ("%d\n", mp[v][k-1]);
}
}
return 0;
}
离散化
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> vec[N];
int a[N], A[N];
int main(void) {
int n, m;
while (scanf ("%d%d", &n, &m) == 2) {
for (int i=1; i<=n; ++i) vec[i].clear ();
for (int i=1; i<=n; ++i) {
scanf ("%d", &a[i]); A[i] = a[i];
}
sort (A+1, A+1+n);
int nn = unique (A+1, A+1+n) - A - 1;
for (int i=1; i<=n; ++i) {
a[i] = lower_bound (A+1, A+1+nn, a[i]) - A;
}
for (int i=1; i<=n; ++i) {
vec[a[i]].push_back (i);
}
for (int k, v, i=1; i<=m; ++i) {
scanf ("%d%d", &k, &v);
v = lower_bound (A+1, A+1+nn, v) - A;
if (vec[v].size () < k) puts ("0");
else printf ("%d\n", vec[v][k-1]);
}
}
return 0;
}
STL UVA 11991 Easy Problem from Rujia Liu?
原文：http://www.cnblogs.com/Running-Time/p/5027060.html