PKU : 3250 - Bad Hair Day

問題概要

http://poj.org/problem?id=3250
身長のばらばらな, N匹の牛が東を向いて, 一直線に並んでいます.
ある牛は, 自分の身長以上の牛の前までの牛の頭なら見ることができます.
各牛が見ることができる牛の数を合計するといくらになるでしょう.

アルゴリズム

stackつかう

• 身長とIDのペアでpushしていく
• スタックのtopの身長以上の牛が出てきたら, topより身長が高い間出せるだけ出す

プログラム

typedef pair<int,int> P; //first:id, second:height

int main(void){
  int n;
  while(scanf("%d",&n) != EOF){
    ll ans = 0;
    stack<P> s;

    rep(i,n+1){
      int x;
      if(i == n) x = 1000000000;
      else scanf("%d",&x);

      while(!s.empty() && s.top().second <= x){
        P p = s.top(); s.pop();
        ans += i - p.first - 1;
      }
      s.push(P(i,x));
    }
    printf("%lld\n",ans);
  }
}