2021年秋季《数据结构》_EOJ 1019.题库整理（已解决）

题目

解法

第一种方法（Time limit exceeded）

开一个大数组a，a[i]表示难度为i的题目个数，查询操作时从后往前找最高难度。在这里为了避免每次从MAXN往回找，用了全局变量maxlev存储入库时的最高难度（由于出库难度为maxlev时难以更新难度，所以不以maxlev为最终方法）。
但部分测试点难度很高，导致数组要开的非常大（1e9还不够），如果出现最高难度和次高难度相差很多时循环很耗时，没法过。

#include <bits/stdc++.h>
using namespace std;#define MAXN 100000001
int a[MAXN] = {
    0};  // 记录难度为i的题目的个数// 注意提示：题库为空时忽略出库操作，查询输出0
int main()
{
    stack<int> st;int maxlev = 0;int n; cin>>n;for(int i = 0; i < n; i++){
    int sig; cin>>sig;switch (sig){
    case 0:  // 入库{
    int lev; cin>>lev;a[lev]++;// cout<<a[11]<<'&'<<endl;if(lev>maxlev) maxlev = lev;  // 更新题库中最高难度st.push(lev);// cout<<st.top()<<'*'<<endl;break;}case 1:  // 出库{
    if(!st.empty()){
    int tmp = st.top();a[tmp]--;  // tmp难度的题目数量减少1st.pop();}break;}case 2:  // 查询{
    if(!st.empty()){
    int j = maxlev;while (j>=1 && a[j]==0) j--;cout<<j<<endl;}else cout<<0<<endl;break;}default:break;}}system("pause");return 0;
}

第二种方法（AC，不过擦边耗时1.855）

抄的
利用stl的*max_element(v.begin(), v.end())返回vector中的最大元素（这波是假stack真vector

第三种方法（AC）

助教nb！
建两个栈，一个栈存每次的操作，另一个栈存每次操作时题库中的最高难度

注意每次出库操作既要判断操作前是否栈空，也要判断操作后是否栈空，以正确地更新最高难度

#include<bits/stdc++.h>
using namespace std;int main()
{
    stack<int> st1;stack<int> st2;  // 记录题库中题目的最大难度int maxlev = 0;int n; cin>>n;for(int i = 0; i < n; i++){
    int sig; cin>>sig;switch (sig){
    case 0:  // 入库int tmp; cin>>tmp;st1.push(tmp);if(tmp>maxlev)maxlev = tmp;  // 更新最大难度st2.push(maxlev);  // 记录最大难度break;case 1:  // 出库if(!st1.empty()){
    st1.pop();st2.pop();if(!st2.empty())  // 更新最高难度maxlev = st2.top();else maxlev = 0;}break;case 2:  // 查询if(!st1.empty()){
    cout<<st2.top()<<endl;}else cout<<0<<endl;break;default:break;}}system("pause");return 0;
}