map的特性是，所有元素都会根据元素的减值自动被排序。map的所有元素都是pair，同时拥有实值(value)和键值(key)。pair的第一个元素会被视为键值，第二个元素会被视为实值。map不允许两个元素拥有相同的键值。
map的基本构造函数
map添加元素
map<int ,string> maplive;
- pair<int,string> value(1,"a")；maplive.insert(value);
等价于maplive.insert(pair<int,string>(1,"a"));
- maplive.insert(map<int,string>::value_type(1,"a"));
- maplive[1]="a";//map中最简单最常用的插入添加！
map的基本操作函数
begin() 返回指向map头部的迭代器
clear() 删除所有元素
count() 返回指定元素出现的次数
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int main(){
map<string,int> strMap;
strMap[string("jjhou")] = 1;
strMap[string("jerry")] = 2;
strMap[string("jason")] = 3;
strMap[string("jimmy")] = 4;
pair<string,int> value(string("david"),5);
strMap.insert(value);
for(map<string,int>::iterator it = strMap.begin();it !=strMap.end();it++)
{
cout<<it->first<<' '<<it->second<<endl;
}
cout<<endl;
int number = strMap[string("jjhou")];
cout<<number<<endl;
cout<<endl;
map<string,int>::iterator iter1;
iter1 = strMap.find(string("mchen"));
if(iter1 == strMap.end())
cout<<"mchen no fount"<<endl;
cout<<endl;
iter1 = strMap.find(string("jerry"));
if(iter1 != strMap.end())
cout<<"jerry fount"<<endl;
cout<<endl;
iter1->second = 9;
int number1 = strMap[string("jerry")];
cout<<number1<<endl;
for(map<string,int>::iterator it = strMap.begin();it !=strMap.end();it++)
{
cout<<it->first<<' '<<it->second<<endl;
}
cout<<endl;
strMap.erase(iter1);
strMap.erase(string("jason"));
map<string,int>::iterator strmap_iter2 = strMap.begin();
for(;strmap_iter2 !=strMap.end();strmap_iter2++)
{
cout<<strmap_iter2->first<<' '<<strmap_iter2->second<<endl;
}
return 0;
}
|
map用的最多的还是key排序和value排序。这里我们重点讲value排序。
我们可能想到要用sort函数来排序，但是直接用的话又不可以，
这里我们就需要用vector来进行排序.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<iostream>
#include<algorithm>
#include<stdio.h>
#include <vector>
#include<string>
#include<map>
#include <functional>
using namespace std;
bool cmp(const pair<string, int>& a, const pair<string, int>& b) {
return a.second < b.second;
}
int main()
{
map<string, int> name_score_map;
name_score_map["LiMin"] = 90;
name_score_map["ZiLinMi"] = 79;
name_score_map["BoB"] = 92;
name_score_map.insert(make_pair("Bing", 99));
name_score_map.insert(make_pair("Albert", 86));
map<string, int>::iterator iter;
for (iter = name_score_map.begin(); iter != name_score_map.end(); ++iter) {
cout << (*iter).first << endl;
}
cout << endl;
vector<pair<string, int>> vec(name_score_map.begin(), name_score_map.end());
sort(vec.begin(), vec.end(), cmp);
for (int i = 0; i < vec.size(); ++i)
cout << vec[i].first << endl;
system("pause");
return 0;
}
|
理解之后，我们可以看下下面的题：
题目链接
题目描述
世博会志愿者的选拔工作正在 A
市如火如荼的进行。为了选拔最合适的人才，AA市对
所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根
据计划录取人数的150%150%划定，即如果计划录取mm名志愿者，则面试分数线为排名第m×150%m×150%
（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有
选手。
现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。
输入输出格式
输入格式：
第一行，两个整数
n,m(5≤n≤5000,3≤m≤n)n,m(5≤n≤5000,3≤m≤n)，中间用一个空格隔开，其
中nn表示报名参加笔试的选手总数，mm表示计划录取的志愿者人数。输入数据保证
m×150% 向下取整后小于等于 n。
第二行到第 n+1n+1
行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号
k(1000≤k≤9999)k(1000≤k≤9999)和该选手的笔试成绩s(1≤s≤100)s(1≤s≤100)。数据保证选手的报名号各不相同。
输出格式：
第一行，有22个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。
从第二行开始，每行包含22个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。
输入样例：
6 3
1000 90
3239 88
2390 95
7231 84
1005 95
1001 88
输出样例：
88 5
1005 95
2390 95
1000 90
1001 88
3239
88
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
if(a.second==b.second)
return a.first>b.first;
else return a.second < b.second;
}
int main()
{
int n,m,cnt=0;
cin >> n>>m;
int a[n],b[n];
map<int,int>p;
for(int i=0;i<n;i++){
cin >> a[i]>>b[i];
p[a[i]]=b[i];
}
vector<pair<int,int> >sore(p.begin(),p.end());
sort(sore.begin(),sore.end(),cmp);
int link=floor((m-1)*1.50);
int fenlink = sore[n-link-1].second;
for(int i=0; i<sore.size(); i++){
if(sore[i].second >= fenlink) {
cnt++;
}
}
cout << fenlink << " "<< cnt << endl;
for(int i=sore.size()-1;i>=0;i--){
if(sore[i].second >= fenlink) {
cout << sore[i].first << " "<<sore[i].second << endl;
}
}
return 0;
}
|