「BZOJ1660」[Usaco2006 Nov] Bad Hair Day 乱发节
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
53+0+1+0+1=5
题解
单调栈水题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include<iostream> #include<cstdio> using namespace std; int n,top,a[80001],s[80001]; long long ans; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { if(a[i]<s[top]) ans+=top; else { while(a[i]>=s[top]&&top) top--; ans+=top; } s[++top]=a[i]; } printf("%lld",ans); return 0; } |
Subscribe
计数器 9724581
OI 课件=>
OI 课件=>