首页 > 代码库 > [poj3250]单调栈 Bad Hair Day
[poj3250]单调栈 Bad Hair Day
解题关键：将每头牛看到的牛头数总和转化为每头牛被看到的次数，然后用单调栈求解，其实做这道题的目的只是熟悉下单调栈
此题为递减栈
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<stack> 6 #include<iostream> 7 using namespace std; 8 typedef long long ll; 9 ll a[80002];10 stack<ll>ss;11 int main(){12 ll n,ans;13 while(cin>>n){14 ans=0; 15 for(int i=0;i<n;i++) cin>>a[i];16 for(int i=0;i<n;i++){17 while(!ss.empty()&&a[i]>=ss.top()){18 ss.pop();19 }20 ans+=ss.size();21 ss.push(a[i]);22 }23 cout<<ans<<endl;24 while(!ss.empty()) ss.pop();25 }26 return 0;27 }
数组实现：
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<iostream> 6 using namespace std; 7 typedef long long ll; 8 ll ss[80002],top; 9 int main(){10 ios::sync_with_stdio(0);11 ll n,t,ans=0;12 while(cin>>n){13 top=-1,ans=0;14 for(int i=0;i<n;i++){15 cin>>t;16 while(top!=-1&&ss[top]<=t) top--;17 ans+=top+1;18 ss[++top]=t;19 }20 cout<<ans<<endl;21 }22 return 0;23 }
[poj3250]单调栈 Bad Hair Day
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。