洛谷 P2866 [USACO06NOV]糟糕的一天Bad Hair Day
题目描述
Some of Farmer John's N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows' heads.
Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.
Consider this example:
=
= =
= - = Cows facing right -->
= = =
= - = = =
= = = = = =
1 2 3 4 5 6 Cow#1 can see the hairstyle of cows #2, 3, 4
Cow#2 can see no cow's hairstyle
Cow#3 can see the hairstyle of cow #4
Cow#4 can see no cow's hairstyle
Cow#5 can see the hairstyle of cow 6
Cow#6 can see no cows at all!
Let ci denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.
农民约翰的某N(1 < N < 80000)头奶牛正在过乱头发节!由于每头牛都意识到自己凌乱不堪 的发型,约翰希望统计出能够看到其他牛的头发的牛的数量.
每一头牛i有一个高度所有N头牛面向东方排成一排,牛N在最前面,而 牛1在最后面.第i头牛可以看到她前面的那些牛的头,只要那些牛的高度严格小于她的高度,而且 中间没有比hi高或相等的奶牛阻隔.
让N表示第i头牛可以看到发型的牛的数量;请输出Ci的总和
输入输出格式
输入格式:
Line 1: The number of cows, N.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i.
输出格式:
Line 1: A single integer that is the sum of c1 through cN.
输入输出样例
6
10
3
7
4
12
2
5 维护一个栈 比当前低的直接覆盖到比他次低的高度
然后统计和
屠龙宝刀点击就送
#include <ctype.h>
#include <cstdio>
#define gt ch=getchar()
#define N 80010 void read(int &x)
{
x=;bool f=;
char ch;gt;
while(!isdigit(ch))
{
if(ch=='-') f=;
gt;
}
while(isdigit(ch))
{
x=x*+ch-'';
gt;
}
x=f?(~x)+:x;
}
int n,h[N],top,stack[N];
int main()
{
read(n);
for(int i=;i<=n;i++) read(h[i]);
h[n+]=<<;
long long ans=;
for(int i=;i<=n+;i++)
{
while(top&&h[stack[top]]<=h[i])
{
ans+=i-stack[top]-;
top--;
}
stack[++top]=i;
}
printf("%lld",ans);
return ;
}
最新文章
- 无法加载 DLL“SQLite.Interop.dll”: 找不到指定的模块。 (异常来自 HRESULT:0x8007007E)
- ASP.NET Web API标准的“管道式”设计
- 【制作镜像】安装VMwareTool
- mac brew 安装包下载失败解决
- DevExpress ASPxHtmlEditor控件格式化并导出Word (修复中文字体导出丢失)
- alt和title的区别与用法
- Eclipse工程有乱码
- vue 中监测滚动条加载数据(懒加载数据)
- Servlet 自定义标签
- Spring initializr使用
- 用C语言实现窗口抖动
- Spring Boot初识(2)- Spring Boot整合Mybaties
- linux 源码编译php的参数
- MySQL子查询慢现象的解决
- js实现excel的解析
- 【C#】构建可枚举类型(IEnumerable和IEnumerator)
- Spring的声明式事务----Annotation注解方式(1)
- 利用HTML5 与CSS3 做的放大镜
- Elasticsearch suggester搜索建议初步
- AutoResetEvent 和 ManualResetEvent 多线程应用