20分玄关

wangxzx @ 2024-05-31 20:08:50

#include<bits/stdc++.h>
using namespace std;
int q,n,a[100001],x;
stack<int> s;
int main()
{
    cin>>q;
    for(int e=1;e<=q;e++)
    {
        n=x;
        if(e==1)
        {
            cin>>n;
        }
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        for(int i=1;i<=n;i++)
        {
            if(i==1)
            {
                cin>>x;
            }
            s.push(a[i]);
            while(!s.empty() && s.top()==x)
            {
                //cout<<s.top()<<endl;
                s.pop();
                cin>>x;
            }
        }
        if(s.empty())
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
            for(int i=1;i<=s.size();i++)
            {
                s.pop();
            }
        }
    }
    return 0;
}

by Tiffake @ 2024-05-31 21:21:28

@SX114514 讨论区不能直接贴题解。

by Tiffake @ 2024-05-31 21:21:57

@ssssbbbbbb 可以，但是不影响

by ssssbbbbbb @ 2024-05-31 21:22:47

@Tiffake 可以帮忙看看这道题吗？

题目描述

在一块空地上紧挨着树立了n堵墙，每堵墙的宽度都为1，高度为h，现要在墙上面贴广告，已知广告牌是一个长方形，现要求广告牌的面积最大。问，最大面积是多少以及广告牌的起点墙和终点墙的位置。

输入格式

第一行n，第二行n个数表示每面墙的高度。

输出格式

第一行长方形的面积。 第二行表示最大面积对应的墙起点和终点，以找到的第一个面积最大的为准

样例 #1

样例输入 #1

5
5 2 4 4 5

样例输出 #1

12
3 5

提示

数据范围：

n<=100000，墙的高度<=10000;

by ssssbbbbbb @ 2024-05-31 21:25:08

@Tiffake 这是我刚刚发的那道题80玄关

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
int r[maxn],top,l[maxn],n,a[maxn];
struct node{
    int val,id;
}st[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    top=0;a[n+1]=0;a[0]=0;
    for(int i=1;i<=n+1;i++){
        while(top>0 && st[top].val>a[i]){
            r[st[top].id]=i-1;
            top--;
        }
        top++;
        st[top].id=i;
        st[top].val=a[i];
    }
    top=0;
    for(int i=n;i>=0;i--){
        while(top>0 && st[top].val>a[i]){
            l[st[top].id]=i+1;
            top--;
        }
        top++;
        st[top].id=i;
        st[top].val=a[i];
    }int ans=0,maxl,maxr;
    for(int i=1;i<=n;i++){
        int t=a[i]*(r[i]-l[i]+1);
        if(ans<t){
            ans=t;
            maxl=l[i];
            maxr=r[i];
        }
    }
    cout<<ans<<endl;
    cout<<maxl<<" "<<maxr<<endl;
    return 0;
}

by wangxzx @ 2024-05-31 21:25:49

@SX114514 谢谢代码，但请删帖，讨论区不许发题解。

by Tiffake @ 2024-05-31 21:34:54

@ssssbbbbbb 考虑 long long

by Tiffake @ 2024-05-31 21:47:47

@ssssbbbbbb 我在校内OJ开 long long 就过了

by Tiffake @ 2024-05-31 21:49:06

@wangxzx 求关（QWQ）

by ssssbbbbbb @ 2024-06-01 23:37:40

@Tiffake 试过了，long long 不行。。。