[数据结构与算法]2021-07-12

今日总结

一、A

1.题解

链接：https://vjudge.net/contest/446142#problem/A

解题思路：定义全局变量数组来标记某元素是否入队，初始化数组元素全为0，输入景点个数，maxi表示最多能选出的景点个数，cnt表示入队列的个数，ans表示出队列的个数，当该景点景观未入队列时，入队列并标记已入队列，cnt++，并取最大选出的景点数，当景点景观已入队列时，将队首元素出队列，ans++，直至某景点景观未入队列为止，再将该元素入队列并标记，最后输出最大景点数。

2.代码

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e6+5;
int z[N];
queue <int> que;

int max(int a,int b)
{
    if(a>=b) return a;
    else return b;
}

int main()
{
    int i,t,n,m,cnt=0,maxi=0,ans=0;
    memset(z,0,sizeof(z));
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>m;
        if(z[m]==0)
        {
            que.push(m);
            z[m]=1;
            cnt++;
            maxi=max(maxi,cnt);
        }
        else
        {
            while(z[m]!=0)
            {
                z[que.front()]=0;
                que.pop();
                ans++;
            }
            que.push(m);
            z[m]=1;
            cnt=cnt-ans+1;
            ans=0;
        }

    }
    cout<<maxi<<endl;
}

二、L

1.题解

链接：https://vjudge.net/contest/446142#problem/L

解题思路：每次输入数据都重新定义队列，输入字符串，当字符串为“enqueue"时，输入元素，并入队列，当字符串为"dequeue"时，先判断队列是否为空，当队列为空时，直接输出结果，不为空时，输出队首元素并出队，当字符串为”query"时，判断队列是否为空，当队列为空时，直接输出结果，不为空时，依次输出队首元素并出队，直至队列为空。

2.代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int main()
{
    string z;
    int i,t,m;
    while(cin>>t)
    {
        queue <int> que;
        for(i=0;i<t;i++)
        {
            cin>>z;
            if(z=="enqueue")
            {
                cin>>m;
                que.push(m);
            }
            else if(z=="dequeue")
            {
                if(que.empty())  cout<<"this is empty!"<<endl;
                else
                {
                    cout<<que.front()<<endl;
                    que.pop();
                }
            }
            else
            {
                if(que.empty())  cout<<"this is empty!"<<endl;
                else
                {
                    while(!que.empty())
                    {
                        cout<<que.front()<<endl;
                        que.pop();
                    }
                }
            }
        }
        cout<<endl;
    }
}

三、O

1.题解

链接：https://vjudge.net/contest/446142#problem/O

解题思路：定义一个全局变量数组来表示出栈的顺序，定义一个函数来比较两个数的大小。每次输入都重新定义栈，maxi用来存储栈最大容量，t表示每次入栈出栈后栈内容量，令q=1，即z[q]表示第一个出栈的元素，按顺序依次入栈，t++,当第一个出栈的元素是栈顶元素时，出栈，t–,用函数取最大容量，再用第二个出栈的元素继续运行。当栈最后为空时，输出最大容量，否则，输出-1。

2.代码

#include <iostream>
#include <stack>
#include <cstdio>
using namespace std;
int z[200];

int max(int a,int b)
{
    if(a>=b) return a;
    else return b;
}

int main()
{
    int i,n;
    while(cin>>n)
    {
        stack <int> sta;
        int j,maxi=0,q=1,t=0;
        for(i=1;i<=n;i++)
        {
            sta.push(i);
            t++;
            cin>>z[i];
            while(q<=i&&z[q]==sta.top())
            {
                maxi=max(maxi,t);
                sta.pop();
                t--;
                q++;
            }
        }
        if(sta.size()==0) cout<<maxi<<endl;
        else cout<<"-1"<<endl;
    }
}