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; } }