9 条题解
-
19
思路
先入后出,很经典的栈操作题。由于数据量大,难度在最大值的求法,暴力搜是不行的。需要引入辅助栈。 辅助栈专门记录栈当前的最大值。如果push值大于辅助栈的头元素,则辅助栈中压入要push的值,否则重复压入辅助栈的头元素。比如: A栈为主栈,输入数据依次入栈:1 2 3 5 4; B栈为辅栈,记录对应的最大值:1 2 3 5 5; 弹出时,两栈同时弹出即可。代码
#include<iostream> #include<stack> using namespace std; stack<int>a; stack<int>b; int n,m,x; int main() { cin>>n; while(n--) { cin>>m; if(m==0) { cin>>x; a.push(x); if(b.empty()||x>b.top()) b.push(x); else b.push(b.top()); } else if(m==1) { if(a.size())a.pop(); if(b.size())b.pop(); } else { if(b.empty()) cout<<0<<endl; else cout<<b.top()<<endl; } } return 0; }
-
4
代码
#include<bits/stdc++.h> using namespace std; int n,oper,x,a[200001],size,maxx; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>oper; if(oper==0) { cin>>x; a[++size]=x; } else if(oper==1) { if(size>0)size--; } else{ for(int j=1;j<=size;j++) maxx=max(maxx,a[j]); cout<<maxx<<endl; maxx=0; } } return 0; }
-
1
这道题的主要任务是实现一个对仓库里货物查询的操作,这里我把此操作封装在了函数中,写在了主函数后面并在前面进行了声明,栈a是仓库,栈b是操作中的一个中间栈 将a清空并归位,便实现了查询操作。因为ans的值初始化为0,而while循环的条件为非空,所以当栈为空时,会输出0,符合题目要求,故不做特殊处理 当然,也可以将查询函数写为void型,直接在函数中输出ans的值即可 用惯了容器,所以不愿用数组模拟栈,望见谅
/* #include <bits/stdc++.h> using namespace std; stack<int> a; int chaxun(); int main() { int n; cin >> n; int zhiling,x; for (int i = 1;i <= n;i++) { cin >> zhiling; if (zhiling == 0) { cin >> x; a.push(x); } else if (zhiling == 1) { if (!a.empty()) { a.pop(); } } else if (zhiling == 2) { cout << chaxun() << "\n";//这里是换行 } } return 0; } int chaxun() { int ans = 0; stack<int> b; while(!a.empty()) { ans = max(ans,a.top()); b.push(a.top()); a.pop(); } while(!b.empty()) { a.push(b.top()); b.pop(); } return ans; }//已AC,请谨慎使用,不要抄袭题解*/
-
-1
日志分析 P1042
本题解为15392178731所创
思路
1.准备
#include <bits/stdc++.h> #define ll long long using namespace std; ll n,x,y; stack<int>s;
2.输入std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n;
重点 输入y1.当y==0,输入x,压入栈。
if (y==0){ cin>>x; s.push(x); }
2.当y==1,输出栈顶元素。
else if (y==1) { if (!s.empty()) { s.pop(); } }
3.当y==2,输出最大元素,也是最难的。
分析
1.暴力
太麻烦×
2.在定义一个b栈,找到最大。
定义函数
int c(){ int ans=0; stack<int>b; while(!s.empty()){ ans=max(ans,s.top()); b.push(s.top()); s.pop(); } while(!b.empty()){ s.push(b.top()); b.pop(); } return ans; }
判断
else if (y==2){ cout<<c()<<endl; }
代码
#include <bits/stdc++.h> 反抄袭 #define ll long long 反抄袭 using namespace std; 反抄袭 ll n,x,y; 反抄袭 stack<int>s; 反抄袭 int c(){ 反抄袭 int ans=0; 反抄袭 stack<int>b; 反抄袭 while(!s.empty()){ 反抄袭 ans=max(ans,s.top()); 反抄袭 b.push(s.top()); 反抄袭 s.pop(); 反抄袭 } 反抄袭 while(!b.empty()){ 反抄袭 s.push(b.top()); 反抄袭 b.pop(); 反抄袭 } 反抄袭 return ans; 反抄袭 } 反抄袭 反抄袭 int main(){ 反抄袭 std::ios::sync_with_stdio(false); 反抄袭 cin.tie(0); 反抄袭 cout.tie(0); 反抄袭 cin>>n; 反抄袭 while(n--){ 反抄袭 cin>>y; if (y==0){ cin>>x; s.push(x); } else if (y==1) { if (!s.empty()) { s.pop(); } } else if (y==2){ cout<<c()<<endl; } } return 0; }
小朋友不能抄袭呦,不然得
吃席 -
-1
#include <stack> #include <string> using namespace std; stack<int> sta,sta0; int n,x,maxx,oper; int main(){ cin>>n; for (int i=1;i<=n;i++){ cin>>oper; if (oper==0){ cin>>x; sta.push(x); maxx=max(x,maxx); } else if (oper==1){ if (!sta.empty())sta.pop(); maxx=0; while (!sta.empty()){ sta0.push(sta.top()); maxx=max(sta.top(),maxx); sta.pop(); } while (!sta0.empty()){ sta.push(sta0.top()); sta0.pop(); } } else cout<<maxx<<endl; } return 0; }
-
-1
用数组模拟栈会好一些(那就不用把整个栈吐空又塞满了)
#include <iostream> #include <stack> #include <string> using namespace std; stack<int> sta,sta0; int n,x,maxx,oper; int main(){ cin>>n; for (int i=1;i<=n;i++){ cin>>oper; if (oper==0){ cin>>x; sta.push(x); maxx=max(x,maxx); } else if (oper==1){ if (!sta.empty())sta.pop(); maxx=0; while (!sta.empty()){ sta0.push(sta.top()); maxx=max(sta.top(),maxx); sta.pop(); } while (!sta0.empty()){ sta.push(sta0.top()); sta0.pop(); } } else cout<<maxx<<endl; } return 0; }
-
-4
首先,我们需要读取日志文件,解析其中的操作,并根据规则进行处理。对于查询操作,我们需要找到当前仓库中的最大集装箱重量。
#include <iostream> #include <vector> #include <algorithm> #include <fstream> using namespace std; int main() { ifstream log("log.txt"); int n; log >> n; log.ignore(); // 忽略换行符 vector<int> weights; int op; while (log >> op) { if (op == 0) { int weight; log >> weight; weights.push_back(weight); } else if (op == 1) { // 出库操作,找到最晚入库的集装箱出库 auto it = max_element(weights.begin(), weights.end()); cout << *it << endl; weights.erase(it); } else if (op == 2) { // 查询操作,输出最大集装箱重量 cout << max_element(weights.begin(), weights.end()) << endl; } } return 0; }
这段代码首先读取日志文件中的操作数,然后根据操作类型进行处理。对于查询操作,我们使用
max_element
函数找到最大集装箱重量,并输出。注意在处理完一个查询操作后,需要将当前仓库中的所有集装箱重量置为0,以准备处理下一个查询操作。 -
-5
当我们处理这个问题时,我们需要模拟集装箱的入库、出库和查询操作,并同时维护一个记录当前仓库内最大集装箱重量的栈。让我们一步一步分析代码的解决方案。
数据结构选择
我们使用两个栈来解决这个问题:
containerStack
栈:用于模拟集装箱的进出操作。maxWeightStack
栈:用于记录当前仓库内最大集装箱重量。
入库操作
对于入库操作(格式1),我们从输入中读取集装箱的重量
weight
,将其入栈containerStack
,然后检查maxWeightStack
栈的状态。如果栈为空,或者weight
大于等于maxWeightStack
栈顶的元素,我们将weight
入栈maxWeightStack
,以保持maxWeightStack
栈顶一直是当前仓库内的最大集装箱重量。出库操作
对于出库操作(格式2),我们从
containerStack
栈中弹出栈顶元素lastIn
。如果lastIn
等于maxWeightStack
栈顶的元素,说明最后入库的集装箱即为最大集装箱,所以我们也需要从maxWeightStack
栈中弹出。这样可以保持maxWeightStack
栈顶一直是当前仓库内的最大集装箱重量。查询操作
对于查询操作(格式3),我们检查
maxWeightStack
栈是否为空。如果不为空,我们输出maxWeightStack
栈顶的元素,即当前仓库内的最大集装箱重量。如果为空,说明仓库中没有集装箱,我们输出 0。算法思路
通过使用上述栈来模拟各种操作,我们可以在一次遍历输入日志的过程中有效地执行集装箱的进出和查询操作。在每一步操作后,栈中的元素保持正确的状态,使得我们可以轻松地进行最大集装箱查询。
因此,这个程序的算法思路是基于栈的模拟和维护,将问题拆解成一系列简单的操作,最终得到正确的输出。
AC代码: (请注意代码里的放抄袭系统😕 )
#include <iostream> #include <stack> using namespace std; //hetao2043796 int main() { int n; cin >> n; stack<int> containerStack; stack<int> maxWeightStack; while(true) { cout << "~不要抄题解啊!~ " << " "; cout << "~禁止抄袭😄 !~ " << " "; } for (int i = 0; i < n; i++) { int op; cin >> op; if (op == 0) { // 入库操作 int weight; cin >> weight; containerStack.push(weight); if (maxWeightStack.empty() || weight >= maxWeightStack.top()) { maxWeightStack.push(weight); } } else if (op == 1) { // 出库操作 if (!containerStack.empty()) { int lastIn = containerStack.top(); containerStack.pop(); if (lastIn == maxWeightStack.top()) { maxWeightStack.pop(); } while(true) { cout << "~不要抄题解啊!~ " << " "; cout << "~㖥ꋬ╫ᡩ䨀㕶Ⴔ䋋⧄ᥡ⬾ ~ " << " "; } } } else if (op == 2) { // 查询操作 if (!maxWeightStack.empty()) { cout << maxWeightStack.top() << endl; } else { cout << "0" << endl; } } } return 0; }
-
-7
#include<iostream> #include<stack> using namespace std; stack<int>a; stack<int>b; int n,m,x; int main() { cin>>n; while(n--) { cin>>m; if(m0) { cin>>x; a.push(x); if(b.empty()||x>b.top()) b.push(x); else b.push(b.top()); } else if(m1) { if(a.size())a.pop(); if(b.size())b.pop(); } else { if(b.empty()) cout<<0<<endl; else cout<<b.top()<<endl; } } return 0; }
- 1
信息
- ID
- 145
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 1527
- 已通过
- 595
- 上传者