专栏文章

7-27作业/重写ren_gao_zu

个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioorwdl
此快照首次捕获于
2025/12/02 22:41
3 个月前
此快照最后确认于
2025/12/02 22:41
3 个月前
查看原文

作业

P1901 发射站

CPP
#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

CPP
#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

CPP
#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 音乐会的等待

CPP
#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;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...