首页 > 代码库 > poj 3250 Bad Hair Day
poj 3250 Bad Hair Day
题目链接：http://poj.org/problem?id=3250
思路分析：
题目要求求每头牛看见的牛的数量之和，即求每头牛被看见的次数和；
现在要求如何求出每头牛被看见的次数？
考虑到对于某头特定的牛来说，看见它的牛一定在它的左边，另外其高度应该大于该牛的高度，所以只需要计算在其左边并高度大于它的牛的数目即可；
考虑构建一个栈，在某头牛入栈时，弹出栈中高度小于它的牛，剩下的牛高度大于它，此时计算栈的长度就可以得到该牛被看见的次数。
代码如下：
#include<iostream>#include<stack>using namespace std;int main(){ int n; int ans = 0; unsigned long height; stack<unsigned long>S; scanf( "%d", &n ); scanf( "%d", &height ); S.push( height ); for ( int i = 1; i < n; i++ ) { scanf( "%d", &height ); while ( !S.empty() && S.top() <= height ) S.pop(); ans = ans + S.size(); S.push( height ); } while ( !S.empty() ) S.pop(); printf( "%u\n", ans ); return 0;}
算法复杂度: O(N)
poj 3250 Bad Hair Day
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。