7-27作业/重写ren_gao_zu

ren_gao_zu · 2025-07-28 11:26:32 · 个人记录

作业

P1901 发射站

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[10000005],v[1000005],sum[1000005];
stack<int>st;
int maxn=0;
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>v[i];
    }
//  for(int i=0;i<=1e6;i++)
//      b1[i]=-1,b2[i]=-1;
    for(int i=1;i<=n;i++)
    {

        while(st.size()&&a[i]>a[st.top()]){
            sum[i]+=v[st.top()];
            st.pop();
        }
        if(st.size()){
            sum[st.top()]+=v[i];
        }
        st.push(i);
    }
    for(int i=1;i<=n;i++){
        maxn=max(maxn,sum[i]);
    }
    cout<<maxn;
    return 0;
}

POJ - 2559 Largest Rectangle in a Histogram

#include<iostream>
#include<algorithm>
#include<stack>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n=1e9,a[N],b1[N],b2[N];
stack<int> st1,st2;
void solve(){
    while(st1.size()){
        st1.pop();
    }
    while(st2.size()){
        st2.pop();
    }
    //cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=0;i<=n;i++)
        b1[i]=0,b2[i]=n+1;
    for(int i=n;i>=1;i--){
        while(st2.size()&&a[i]<=a[st2.top()]){
            st2.pop();
        }if(st2.size()){
            b2[i]=st2.top();
        }st2.push(i);
    }for(int i=1;i<=n;i++){
        while(st1.size()&&a[i]<=a[st1.top()]){
            st1.pop();
        }if(st1.size()){
            b1[i]=st1.top();

        }st1.push(i);
    }int maxn=0;
    for(int i=1;i<=n;i++){
        int l=b1[i],r=b2[i],mian=a[i]*(r-l-1);
        maxn=max(maxn,mian);
    }cout<<maxn<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    while(1){
        cin>>n;
        if(n==0)break;
        solve();
    }return 0;
}

P3467 [POI 2008] PLA-Postering

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=3e5+5;
int n;
int me,a[1000005],ans;
stack<int>st;
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>me>>a[i];
    }
    for(int i=1;i<=n;i++){
        while(st.size()&&a[i]<a[st.top()]){
            st.pop();
            ans++;
        }
        if(st.size()&&a[st.top()]==a[i])continue;
        st.push(i);
    }
    ans+=st.size();
    cout<<ans;
    return 0;
}

重写

P1823 [COI 2007] Patrik 音乐会的等待

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[10000005];
struct node{
    int h,num;
}s[100005];
stack<node>st;
int n;
int sum;
signed main(){

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i].h;
        s[i].num=1;
    }

    for(int i=1;i<=n;i++){
        while(st.size()&&s[i].h>=st.top().h){
            sum+=st.top().num;
            if(s[i].h==st.top().h){
                s[i].num+=st.top().num;
            }
            st.pop();

        }
        if(st.size()){
            sum++;
        }
        st.push(s[i]);
    }
    cout<<sum;
    return 0;
}