首页 > 代码库 > 【BZOJ 1660】 [Usaco2006 Nov]Bad Hair Day 乱发节
【BZOJ 1660】 [Usaco2006 Nov]Bad Hair Day 乱发节
1660: [Usaco2006 Nov]Bad Hair Day 乱发节
Time Limit: 2 Sec Memory Limit: 64 MBSubmit: 678 Solved: 326
[Submit][Status][Discuss]
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
单调队列。
维护一个单减队列，可是要注意求值时假设有相等的，算到与他相等的后一位。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
int n,h[80005];
struct qq
{
int id,v;
}q[80005];
int main()
{
scanf("%d",&n);
for (int i=n;i>=1;i--)
scanf("%d",&h[i]);
long long ans=0;
int r=1;
q[1].v=h[1],q[1].id=1;
q[0].id=0;
for (int i=2;i<=n;i++)
{
while (r>=1&&q[r].v<h[i])
r--;
ans=ans+i-(q[r].id+1);
while (r>=1&&q[r].v==h[i])
r--;
q[++r].id=i,q[r].v=h[i];
}
cout<<ans<<endl;
return 0;
}
【BZOJ 1660】 [Usaco2006 Nov]Bad Hair Day 乱发节
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。