专栏文章
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 条评论,欢迎与作者交流。
正在加载评论...