【map离散化+打表】 UVA11991 Easy Problem from Rujia Liu?

时间:2022-07-13 10:28:20

【map离散化+打表】UVA 11991 Easy Problem from Rujia Liu?

map关联容器:有序 + 映射,查找的复杂度O(nlogn)

题目大意

给你n个数构成的数组,求数v第k次出现的下标值(下标从1开始)

【map离散化+打表】 UVA11991 Easy Problem from Rujia Liu?
【map离散化+打表】 UVA11991 Easy Problem from Rujia Liu?

说一下思路

这题很显然要打表预处理,关键是怎么打这张表

1.首先我们观察到v很大,开一个二维数组data[v][k]肯定存储不了,所以用map离散化(自动有序编号,避免空间浪费)

2.data[v]肯定是一个变长的数组,存储数据v出现0,1,2次……的下标值,想到vector< int >

这样,预处理每个元素的复杂度O(logn),总预处理时间复杂度O(nlogn),每次查询O(logn),所以单比O(n*m)复杂度大大降低

比较:data[ ][ ] 与 vector< int >child[ ] 与 map< int ,vector< int > >
0个动态 1个动态 2个动态

【map离散化+打表】 UVA11991 Easy Problem from Rujia Liu?


参考代码

#include<bits/stdc++.h>
using namespace std;

const int _max = 1e3 + 10;
int n,m,v,k;
map<int,vector<int> >mp;//最后两个>>不要连写,会被误认为位运算>>

int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif // ONLINE_JUDGE
while(scanf("%d%d",&n,&m) == 2){
mp.clear();
for(int i = 0; i < n; ++ i){
scanf("%d",&v);
mp[v].push_back(i + 1);//复杂度O(nlogn)
}
for(int i = 0; i < m; ++ i){
scanf("%d%d",&k,&v);
if(mp[v].size() < k) puts("0");
else printf("%d\n",mp[v][k-1]);
}
}
return 0;
}
  • 加粗 Ctrl + B
  • 斜体 Ctrl + I
  • 引用 Ctrl + Q
  • 插入链接 Ctrl + L
  • 插入代码 Ctrl + K
  • 插入图片 Ctrl + G
  • 提升标题 Ctrl + H
  • 有序列表 Ctrl + O
  • 无序列表 Ctrl + U
  • 横线 Ctrl + R
  • 撤销 Ctrl + Z
  • 重做 Ctrl + Y