Codeforces #189 Div2 D "Psychos in a Line"
問題
http://codeforces.com/contest/320/problem/D
訳
n人のサイコが一列に並んでいる。各サイコは一意な1~nのIDが割り当てられている。各ターンに、自分の右隣のサイコよりも大きいIDを持った各サイコは、右隣のサイコを殺す。殺すと同時に殺されるかサイコもいる可能性がある。
あなたは一列に並んだサイコに割り当てられたIDが与えられる。誰も殺せなくなるまで何ターンかかるかを計算せよ。
制約
1 <= n <= 10^5
ソースコード
int main() { // 入力 cin >> n; for (int i = 0; i < n; i++) { cin >> id[i]; } // 謎・・・ stack< pair<int, int> > live; live.push( make_pair(id[n-1], 0) ); int res = 0; for( int i = n - 2; i >= 0; i-- ){ int op = 0; while( !live.empty() ){ int lid = live.top().first; int lop = live.top().second; // 自分よりIDが大きければ自分を乗せて終了 if( id[i] < lid ){ break; } // 自分よりIDが小さければ潰して操作回数+1 live.pop(); op = max( op + 1, lop ); } res = max( res, op ); live.push( make_pair(id[i], op) ); } cout << res << endl; }