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

客官°小女子只卖身不卖艺 2022-12-10 01:29 130阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjI0OTg5_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjI0OTg5_size_16_color_FFFFFF_t_70_pic_center 1]

//我们会首先想到开一个二维数组
    //但是10^5 * 10^5 不论在栈中还是在堆中都会爆掉
    //因此我们要想出节省空间的方法
    #include <iostream>
    #include <vector>
    const int MAX = 100001;
    using namespace std;
    struct node{ 
    	//我们用动态数组来节省空间 
    	vector<int> num, k;  //num代表格子，k代表物品
    	// 索引 0 1 2 
    	// num 800 1000 200 
    	// k 3 4 5 
    	//我们在某个柜子第800格子存入物品3，第1000格子存入物品4 。。。。。
    	//这样我们只用了3个空间，极大节省了空间 
    	int s = 0;   //用s来存储物品的数目 
    }desk[MAX];
    //desk代表柜子 
    int main(){ 
    	int n, q;
    	cin >> n >> q;
    	int a, b, c, d;
    	while (q--){ 				//q次询问 
    		cin >> a;
    		if (a == 1){ 
    			cin >> b >> c >> d;
    			desk[b].s++;
    			desk[b].num.push_back(c);
    			desk[b].k.push_back(d);
    		}
    		else{ 
    			cin >> b >> c;
    			int i;
    			//为什么要倒着来？
    			//因为可能会有物品更新
    			//例如 1 1 1 2 在第一个柜子的第一个格子中存入物品2
    			// 1 1 1 3 在第一个柜子的第一个格子中存入物品3，这时就发生了物品的更新
    			//我们要输出的是3而非2故要由末尾开始遍历 
    			for (i = desk[b].s - 1; i >= 0; i--){ 
    				if (desk[b].num[i] == c){ 
    					cout << desk[b].k[i] << endl;
    					break;
    				}
    			}
    		}
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjI0OTg5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/bb0d064a1980474285cd619231fc75e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjI0OTg5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/1253d5dccb954e6ab277a6198073f33a.png