POJ——T 3250 Bad Hair Day
http://poj.org/problem?id=3250
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 19619 | Accepted: 6702 |
Description
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.
Input
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i.
Output
Sample Input
6
10
3
7
4
12
2
Sample Output
5
Source
#include <algorithm>
#include <iostream>
#include <cstdio> using namespace std; #define LL long long
const int N();
LL Stack[N],top,ans; int main()
{
LL n; cin>>n;
for(LL h,i=;i<=n;i++)
{
cin>>h;
for(;top&&Stack[top]<=h;) top--;
ans+=top; Stack[++top]=h;
}
cout<<ans;
return ;
}
最新文章
- React-native 学习记录
- 每天一个linux命令(22):find 命令的参数详解
- php操作redis
- UITableView常见 UI 问题总结
- 1秒30000QPS,前后端设计思路
- ITK 4.8.1 Qt 5.4 MinGW 4.9.1 Configuration 配置
- oracle添加数据时主键自动增长
- Poweroff – 很好很强大的定制关机工具
- EL表达式在JS中取出来打印[object HTMLDivElement]的问题
- swiper,animate使用方法
- [置顶] 单键模式的C++描述
- BCB实现BMP图片的RGB分解(转)
- Scala入门系列(五):面向对象之类
- <;转>;年终盘点!2017年超有价值的Golang文章
- Stm32之通用定时器复习
- 4 扩展库Scipy
- python写的翻译代码
- app自动化测试Appium+python
- 关于git中Pageant开机启动且自动关联秘钥
- C++使用thread类多线程编程