前置知识 pair+map

一、pair是STL中的二元结构体,有两个参数,分别对应first和second的数据类型,它们可以是任意基本数据类型或者STL容器。定义一个pair的方法为:pair<typename1,typename2> name;
pair会自动将first从小到大排序,如果first相同,则按second从小到大排序。

pair<int,int>a;
取出pair中的第一个成员变量是 a.first;
取出pair中的第二个成员变量是 a.second;

二、map翻译为映射,是STL中的常用容器,定义一个map的方法为:map<typename1,typename2> name;
其中,typename1是映射前的类型(键key),typename2是映射后的类型(值value),name为映射的名字。map可以将任何基本类型(包括STL容器)映射到任何基本类型(包括STL容器)。
map在建立映射的同时,会自动按照键key从小到大排序。

map<int,int>a;
取出map中的键(key)是 a->first;
取出map中的值(value)是 a->second;

在map与pair嵌套的时候一定要搞清楚是用 ->(箭头) 还是用 .(点) 取成员变量,pair是用点,map是用箭头。

map的二维表示和迭代器遍历(正序/逆序)

输入:第一行输入一个整数n,表示有n个点。
接下来n行,每行输入两个整数x,y(-1e18<=x,y<=1e18),表示n个点的坐标为(x,y),统计每个点出现的次数。

6
50000000000000000 -40000000000000000
50000000000000000 -40000000000000000
50000000000000000 -40000000000000000
50000000000000000 -30000000000000000
50000000000000000 -30000000000000000
40000000000000000 -30000000000000000

输出:将x从小到大排序,如果x相同,则按y从小到大排序。正向遍历一次,反向遍历一次,每行输出(x,y)及其出现次数。

正向遍历
40000000000000000 -30000000000000000 1
50000000000000000 -40000000000000000 3
50000000000000000 -30000000000000000 2
反向遍历
50000000000000000 -30000000000000000 2
50000000000000000 -40000000000000000 3
40000000000000000 -30000000000000000 1

方法1,map嵌套pair,二元结构体pair当下标(map的键)

定义map<pair<ll,ll>,int>vis; pair会自动将first从小到大排序,如果first相同,则按second从小到大排序。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,x,y;
map<pair<ll,ll>,int>vis;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y;
        vis[{x,y}]++;//结构体当下标
    }
    printf("\n正向遍历\n");
    map<pair<ll,ll>,int>::iterator it;
    for(it=vis.begin();it!=vis.end();it++)//正向遍历
        printf("%lld %lld %d\n",it->first.first,it->first.second,it->second);
        //输出x,y,{x,y}出现次数
    printf("反向遍历\n");
    map<pair<ll,ll>,int>::reverse_iterator re_it;//注意反向遍历写的是reverse_iterator
    for(re_it=vis.rbegin();re_it!=vis.rend();re_it++)//反向遍历
        printf("%lld %lld %d\n",re_it->first.first,re_it->first.second,re_it->second);
        //输出x,y,{x,y}出现次数
    return 0;
}

方法2,map嵌套map,当二维数组用

定义map<ll,map<ll,int> >vis; 相当于建立了两重映射,第一次是从x映射到y,第二次是从y映射到(x,y)出现的次数。既然两个都是map,那么在每次建立映射时会自动按key从小到大排序,从而实现:将x从小到大排序(第一次映射),如果x相同,则按y从小到大排序(第二次映射)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,map<ll,int> >vis;
ll n,x,y;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y;
        vis[x][y]++;
    }
    map<ll,map<ll,int> >::iterator i;
    map<ll,int>::iterator j;
    printf("\n正向遍历\n");
    for(i=vis.begin();i!=vis.end();i++)
        for(j=i->second.begin();j!=i->second.end();j++)
            printf("%lld %lld %d\n",i->first,j->first,j->second);
    map<ll,map<ll,int> >::reverse_iterator re_i;
    printf("反向遍历\n");
    for(re_i=vis.rbegin();re_i!=vis.rend();re_i++)//i需要倒序,j不需要
        for(j=re_i->second.begin();j!=re_i->second.end();j++)
            printf("%lld %lld %d\n",re_i->first,j->first,j->second);
    return 0;
}