洛谷P3613 【深基15.例2】寄包柜

题目链接：https://www.luogu.com.cn/problem/P3613；

首先用想到的是二维数组，其实我的第一感觉也是二维数组，但是很不幸，数据范围太大绝对会导致程序爆掉，导致MLE，所以保险的做法是STL中的map和vector做法

这里只介绍vector做法：

#include<bits/stdc++.h>
using namespace std;
int n,q;
struct node
{
    //用二维数组必炸，因为数据范围太大了 
    vector<int >l;//表示第l个格子存入物品 
    vector<int >s;//表示该格子存入的物品 
    int cnt=0;//表示该已存过cnt次物品 
}guizi[100010];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>q;
    while(q--)
    {
        int a,b,c,d;
        cin>>a;
        if(a==1)
        {
            cin>>b>>c>>d;
            guizi[b].cnt++;//存cnt次 
            guizi[b].l.push_back(c);//放入c格子 
            guizi[b].s.push_back(d);//存物品d 
        }
        else
        {
            cin>>b>>c;
            for(register int i=guizi[b].cnt-1;i>=0;i--)//从后往前，因为格子存放会有更新
            {
                if(guizi[b].l[i]==c)//如果查询到该柜子的格子 
                {
                    cout<<guizi[b].s[i]<<endl;//输出物品 
                    break;//因此时是最新的存放情况，所以有解后需要直接退出查询 
                }
            }
        }
    }
    return 0;
}

洛谷P3613 【深基15.例2】寄包柜

推荐阅读