【map离散化+打表】UVA 11991 Easy Problem from Rujia Liu?
map关联容器:有序 + 映射,查找的复杂度O(nlogn)
题目大意
给你n个数构成的数组,求数v第k次出现的下标值(下标从1开始)
–
说一下思路
这题很显然要打表预处理,关键是怎么打这张表
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个动态
参考代码
#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