ACM.map

青旅半醒 2023-07-06 10:26 3阅读 0赞

## 基本含义 ##

map翻译为映射，是STL中的常用容器。其实，数组就是一种映射，比如：int a\[100\]；就是定义了一个int到int的映射。而a\[5\]=25;就是把5映射到25。数组总是将int类型映射到其它基本类型（称为数组的基类型），这同时也带来了一个问题，有时候我们希望把string映射成一个int，数组就不方便了。这时就可以使用map，map可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）。

## 常见用途 ##

1）需要建立字符（串）与整数之间的映射，使用 map 可以减少代码量。  
2）判断大整数（比如几千位）或者其他类型数据是否存在，可以把map当布尔型数组使用（哈希表），用桶排序时无法开范围特别大的数组。  
3）字符串与字符串之间的映射。

## 使用方法 ##

定义一个map的方法为：map<typename1,typename2> name;  
其中，typename1是映射前的类型（键key），typename2是映射后的类型（值value），name为映射的名字。  
普通int数组a就是map<int,int> a。而如果是字符串到整型的映射，就必须使用string，而不能使用char，即map<string,int> a。map的键和值也可以是STL容器，比如：map<set,string> mp。当然，map的键和值都是唯一的。

## map的访问 ##

通过下标访问就像普通的数组元素访问，例如先定义map<char,int> mp，然后就可以通过mp\[‘c’\]的方式来访问它对应的元素，如mp\[‘c’\]=124。  
通过迭代器访问，先作如下定义：  
map<typename1,typename2>::iterator it；  
因为map的每一对映射都有两个typename，所以，我们使用“it->first”来访问键，而使用“it->second”来访问值。  
例如：  
map<string, int>::iterator p = m.begin();  
p->first; // 这个是 string 值是 “one”  
p->second; //这个是 int 值是 1

## map的常用函数 ##

（1）find()和 size()  
find(key)是返回键为 key 的映射的迭代器，时间复杂度为 0(log 2 n)，n 为 map 中映射的对数。size()用来获得map中映射的对数，时间复杂度为O(1)。  
（2）clear()  
clear()用来清空 map，时间复杂度为 0(n)。  
（3）erase()  
erase()可以删除单个元素，也可以删除一个区间内的所有元素。  
删除单个元素可以用：erase(it)，it为要删除的元素的迭代器，时间复杂度为O(1)。  
也可以用：erase(key)，key为要删除的映射的键，时间复杂度为O(log2n)。  
删除一个区间内的所有元素用：erase(first，last)，first为区间的起始迭代器，last为区间的末尾迭代器的下一个地址，也就是左闭右开的区间\[first,last)，时间复杂度为O(last-first)。

## pair的定义 ##

pair 是“二元结构体”的替代品，将两个元素捆绑在一起，节省编码时间。相当于以下定义：  
struct pair\{  
typename1 first;  
typename2 second;  
\}  
pair有两个参数，分别对应first和second的数据类型，可以是任意基本数据类型或者容器。  
定义一个pair的方法为：  
pair<typename1,typename2> name;

## 例题 ##

**保龄球-map**  
Problem:A  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
DL 算缘分算得很烦闷，所以常常到体育馆去打保龄球解闷。因为他保龄球已经打了几十年了，所以技术上不成问题，于是他就想玩点新花招。  
DL 的视力真的很不错，竟然能够数清楚在他前方十米左右每个位置的瓶子的数量。他突然发现这是一个炫耀自己好视力的借口——他看清远方瓶子的个数后从某个位置发球，这样就能打倒一定数量的瓶子。  
1 OOO  
2 OOOO  
3 O  
4 OO  
如上图，每个“O”代表一个瓶子。如果 DL 想要打倒 3 个瓶子就在 1 位置发球，想要打倒 4 个瓶子就在 2 位置发球。  
现在他想要打倒 m 个瓶子。他告诉你每个位置的瓶子数，请你给他一个发球位置。  
Input  
第一行包含一个正整数 n，表示位置数。  
第二行包含 n 个正整数，第 i 个数。表示第 i 个位置的瓶子数，保证各个位置的瓶子数不同。  
第三行包含一个正整数 Q，表示 DL 发球的次数。  
第四行至文件末尾，每行包含一个正整数 m，表示 DL 需要打倒 m 个瓶子。  
Output  
共 Q 行。每行包含一个整数，第 i 行的整数表示 DL 第 i 次的发球位置。若无解，则输出 0。  
Sample Input  
5  
1 2 4 3 5  
2  
4  
7  
Sample Output  
3  
0  
【数据范围】  
对于 50%的数据，1 ≤ n,Q ≤ 1000，1 ≤ai,M ≤ 10^5  
对于 100%的数据，1 ≤ n,Q ≤ 100000，1 ≤ai,M ≤ 10^9

由于数据范围很大，无法开数组实现对应关系，所以使用map。

#include <bits/stdc++.h>
    using namespace std;
    int m,n;
    const int N=1e5+10;
    map<int,int>vis;
    int main()
    {
        
        int n,num,a[N],cnt=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
        
            scanf("%d",&num);
            vis[num]=i;//对应关系
        }
        int q;
        scanf("%d",&q);
        for(int i=1;i<=q;i++)
        {
        
            scanf("%d",&num);
            if(vis[num])
            a[++cnt]=vis[num];
            else
            {
        
                a[++cnt]=0;
            }
        }
        for(int i=1;i<=cnt;i++)
        {
        
            printf("%d\n",a[i]);
        }
        return 0;
    }

**查字典**  
Problem:B  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
小明正在复习全国英语四级考试，他手里有一本词典，现在有很多单词要查。请编写程序帮助他快速找到要查的单词所在的页码。  
Input  
第 1 行 1 个正整数 N，N≤10000，表示字典中一共有多少单词。  
接下来每两行表示一个单词，其中：  
第 1 行是一个长度小于或等于 100 的字符串，表示这个单词，全部小写字母，单词不会重复。  
第 2 行是 1 个整数，表示这个单词在字典中的页码。  
接下来的一行是 1 个整数 M，M≤10000，表示要查的单词数。接下来的 M 行，每行一个字符串，表示要查的单词，保证在字典中存在。  
Output  
M 行，每行一个正整数，表示第 i 个单词在字典中的页码。  
Sample Input  
2  
scan  
10  
word  
15  
2  
scan  
word  
Sample Output  
10  
15

#include <bits/stdc++.h>
    using namespace std;
    map<string,int>vis;
    int main()
    {
        
        int n,page,m;
        ios::sync_with_stdio(false);
        string word,input;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
        
            cin>>word>>page;
            vis[word]=page;
        }
        cin>>m;
        while(m--)
        {
        
            cin>>input;
            cout<<vis[input]<<endl;
        }
        return 0;
    }

眼红的Medusa  
Problem:C  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
虽然Miss Medusa到了北京，领了科技创新奖，但是他还是觉得不满意。原因是，他发现很多人都和他一样获了科技创新奖，特别是其中的某些人，还获得了另一个奖项——特殊贡献奖。而越多的人获得了两个奖项，Miss Medusa就会越眼红。于是她决定统计有哪些人获得了两个奖项，来知道自己有多眼红。  
Input  
输入第一行，有两个数n,m，表示有n个人获得科技创新奖，m个人获得特殊贡献奖。  
第二行，n个正整数，表示获得科技创新奖的人的编号  
第三行，m个正整数，表示获得特殊贡献奖的人的编号  
Output  
输出一行，为获得两个奖项的人的编号，按在科技创新奖获奖名单中的先后次序输出。  
注意：本题答案输出一行，最后不需要换行，否则会Presentation Error  
Sample Input  
4 3  
2 15 6 8  
8 9 2  
Sample Output  
2 8  
Hint  
对于60%的数据，n<=1000，m<=1000  
对于100%的数据，n<=100000，m<=100000，获得奖项的人的编号在2e9以内  
输入数据保证第二行任意两个数不同，第三行任意两个数不同。

注意按在科技创新奖获奖名单中的先后次序输出，写对应关系的时候调整位置。

#include <bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    map<int,int>vis;
    int n,m,cnt,a[N],b[N],ans[N];
    int main()
    {
        
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=m;i++)
            cin>>b[i],vis[b[i]]=1;
        for(int i=1;i<=n;i++)
            if(vis[a[i]])ans[++cnt]=a[i];//根据a数组的大小顺序输出，所以对应是应该将a对应。
        for(int i=1;i<=cnt;i++)
            i==cnt?printf("%d",ans[i]):printf("%d ",ans[i]);
        return 0;
    }

ACM.map

发表评论取消回复

还没有评论，来说两句吧...

相关阅读