首页 > 代码库 > BZOJ1660: [Usaco2006 Nov]Bad Hair Day 乱发节
BZOJ1660: [Usaco2006 Nov]Bad Hair Day 乱发节
1660: [Usaco2006 Nov]Bad Hair Day 乱发节
Time Limit: 2 Sec Memory Limit: 64 MBSubmit: 606 Solved: 289
[Submit][Status]
Description
.jpg)
Input
* Line 1: 牛的数量 N。
* Lines 2..N+1: 第 i+1 是一个整数，表示第i头牛的高度。
Output
* Line 1: 一个整数表示c[1] 至 c[N]的和。
Sample Input
6
10
3
7
4
12
2
输入解释:
六头牛排成一排，高度依次是 10, 3, 7, 4, 12, 2。
10
3
7
4
12
2
输入解释:
六头牛排成一排，高度依次是 10, 3, 7, 4, 12, 2。
Sample Output
5
3+0+1+0+1=5
3+0+1+0+1=5
HINT
Source
Silver
题解：
单调栈水过。。。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 80000+10014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 using namespace std;19 inline int read()20 {21 int x=0,f=1;char ch=getchar();22 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}23 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}24 return x*f;25 }26 int main()27 {28 freopen("input.txt","r",stdin);29 freopen("output.txt","w",stdout);30 int n=read(),a[maxn],sta[maxn];31 for(int i=1;i<=n;i++)a[i]=read();32 a[n+1]=inf;33 int top=0;34 ll ans=0;35 for(int i=1;i<=n+1;i++)36 {37 while(top>0&&a[i]>=a[sta[top]])ans+=i-sta[top--]-1;38 sta[++top]=i;39 }40 printf("%lld\n",ans);41 return 0;42 }
BZOJ1660: [Usaco2006 Nov]Bad Hair Day 乱发节
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。