AOJ : 0551 - Icicles (つらら)

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0551
日本語の問題文なので, 説明省略です.

アルゴリズム

Greedyに, 一番長いつららから落としていくように解きました.
これを実現するために, PriorityQueueを使っています.
一番長いつららが落ちたら, その隣のつららで, 伸びるつららをキューに詰めます.
あとは, 全部落ちきるまでこれを繰り返します.

プログラム

typedef pair<int,int> P; //first:つららの長さ, second:左から数えて何番目か

int n,m;
int t[100002];
const P INF(-1,-1);

//idx番目のつららが, 伸びるかどうかの判定
bool check(int idx){
  if(idx == 0) return t[1] < t[0];
  if(idx == n-1) return t[n-2] < t[n-1];
  return t[idx-1] < t[idx] && t[idx+1] < t[idx];
}

//idx番目のつららが伸びるならば, そのつららを返す
P getNext(int idx){
  if(idx < 0 || n <= idx || !check(idx)) return INF;
  return P(t[idx],idx);
}

int main(){
  while(cin>>n>>m){
    rep(i,n) cin>>t[i];

    int now = 0;
    priority_queue<P> q; //現在伸びているつらら
    rep(i,n) if(check(i)) q.push(P(t[i],i)); //伸びるつららを全てキューに入れる

    while(!q.empty()){
      P p = q.top(); q.pop();

      int plus = m - (p.first + now); //つららが落ちるまでの時間
      if(plus > 0)
        now += plus;
      else
        plus = 0;

      t[p.second] = 0; //今見たつららを落とす
      P left = getNext(p.second-1); //左隣
      P right = getNext(p.second+1); //右隣

      if(left != INF){
        left.first -= now;
        q.push(left);
      }
      if(right != INF){
        right.first -= now;
        q.push(right);
      }
    }

    cout<<now<<endl;
  }
}