大致题意:
一排共n头牛排队站在一起,给出队伍中每头牛的高度。每头牛只能看到站在他右边且个头比他小的牛。求出所有牛可以看到的牛数之和。
大致思路:
做到poj3415,居然碰到“单调栈”这种牛逼的玩意,于是专门来把这道题切掉。所谓单调栈也就是每次加入一个新元素时,把栈中小于等于这个值的元素弹出。接下来回到这道题。求所有牛功能看到多少牛,可以转化为:这n头牛共能被多少头牛看见。当我们新加入一个高度值时,如果栈中存在元素小于新加入的高度值,那这个牛肯定看不见这个高度的牛,就把这个元素弹出。每次加入新元素,并执行完弹出操作后,栈中元素个数便是可以看见这个牛的“牛数”~~~。
#include<cstdio>
#include<cstring>
#include<stack>
#include<iostream>
using namespace std;
stack<long long>sta;
int main(){
long long num,n,i,ans;
while(scanf("%lld",&n)!=EOF){
ans=0;
scanf("%lld",&num);
sta.push(num);
for(i=1;i<n;i++){
scanf("%lld",&num);
while(!sta.empty()&&sta.top()<=num){
sta.pop();
}
ans+=sta.size();
sta.push(num);
}
printf("%lld\n",ans);
while(!sta.empty())sta.pop();
}
return 0;
}
分享到:
相关推荐
- POJ 2528、POJ 2828:栈的基本操作与应用场景。 #### 队列 - **题目示例**: - POJ 2777、POJ 2886:队列的应用。 #### 树状数组 - **题目示例**: - POJ 3264、POJ 3368:树状数组的构造与更新。 #### 字符...
- POJ 1936: 栈的高级用法 - **队列**:适用于先进先出(FIFO)的数据结构。 - **示例题目**: - POJ 2388: 队列的基础操作 - POJ 2299: 队列的复杂应用 - **哈希表**:适用于快速查找的数据结构。 - **示例题目*...
【标题】"POJ2092:计数排序,求第K大的元素"是一个编程题目,主要涉及计数排序算法以及如何在数组中找出第K大的元素。计数排序是一种非基于比较的排序算法,它适用于整数排序,尤其在数据范围不大的情况下效率极高。...
### 单调栈与单调队列详解 #### 一、单调栈 **定义:** 单调栈是一种特殊的数据结构,其内部存储的元素按照单调递增或单调递减的方式排序。当有新的元素需要加入栈时,若这个元素破坏了当前栈内元素的单调性,则...
- (poj1860, poj3259, poj1062, poj2253, poj1125, poj2240):介绍迪杰斯特拉算法(Dijkstra)、贝尔曼-福特算法(Bellman-Ford)、弗洛伊德算法(Floyd)等。 - 使用堆优化的迪杰斯特拉算法。 3. **最小生成树...
- poj3273: 涉及二分法求解单调函数问题。 #### 七、计算几何学 ##### 1. 几何公式 - **定义**: 包括点线面的基本公式等。 - **应用场景**: 在图形学、计算机辅助设计等领域应用广泛。 - **示例题目**: - poj...
这是西北工业大学的POJ试题的答案,欢迎下载!
* 二分法求解单调函数相关知识:例如 poj3273、poj3258、poj1905、poj3122。 计算几何学 1. 几何公式。 2. 叉积和点积的运用:例如 poj2031、poj1039。 3. 多边型的简单算法(求面积)和相关判定(点在多边型内,...
POJ 2703:选择出行方式 **题目概述**: 本题目旨在通过编程的方式解决一个实际问题——选择最佳出行方式(步行或骑自行车)。题目给出了一种算法来决定在不同条件下应该采取哪种出行方式。 **代码解析**: - **...
网上整理的一些poj刷题指南。 poj地址:http://poj.org
4.1 最大乘积问题 4.2 魔术数字游戏 4.3 Jimmy's Bad Day 5.1 循环赛的日程表问题 5.2 猴子选大王 5.3 售货员的难题 6.1 最大字段和问题 6.2 N*N方阵 6.3 埃及分数最好表达式
【标题】"poj.org算法题解集合"是关于在poj.org平台上解决的各种算法问题的集合,这个资源主要是为了帮助编程爱好者和学习者提升算法技能。poj.org是一个著名的在线编程竞赛平台,它提供了丰富的算法题目供用户实践...
《POJ 5346:四则运算表达式求值——栈与队列的应用》 在编程竞赛中,POJ 5346是一道经典的算法题目,它要求我们设计一个程序,能够处理四则运算表达式并计算其值。这个任务涉及到计算机科学中的数据结构——栈和...
- **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...
### ACM新手刷题攻略之POJ ... - 推荐题目:[poj1860](https://vjudge.net/problem/POJ-1860)、[poj3259](https://vjudge.net/problem/POJ-3259)、[poj1062](https://vjudge.net/problem/POJ-1062)、[poj2253]...
* 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...
根据给定的文件信息,我们可以总结出一份详细的IT知识训练计划,主要针对编程竞赛和算法学习,特别是聚焦于POJ(Problem Online Judge)平台上的题目训练。这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165...
1. POJ1274: 农夫John的高科技谷仓问题实质上是一个二分图的最大匹配问题。奶牛和畜栏分别代表二分图的两边,如果一头奶牛可以去某个畜栏产奶,那么就在它们之间建立边。目标是找到最大的匹配数,即最多可以同时有...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...