STL UVA 11991 Easy Problem from Rujia Liu?-白红宇

STL UVA 11991 Easy Problem from Rujia Liu?

阅读量：6274 次

发布时间：2019-06-22

本文共 1190 字，大约阅读时间需要 3 分钟。

题意:训练指南P187

分析:用vector存id下标,可以用map,也可以离散化用数组存(发现不用离散化也可以)

map

#include 
     
      using namespace std;map

>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

(); 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 
     
      using namespace std;const int N = 1e5 + 5;vector
      
        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;}

转载于:https://www.cnblogs.com/Running-Time/p/5027060.html

你可能感兴趣的文章