Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1127-d46a9ecd
この記事にトラックバックする(FC2ブログユーザー)

SPOJ 227 - Ordering the Soldiers [ORDERS] (この記事を編集する[管理者用])

Source

DASM Programming League 2004, problemset 2
SPOJ 227 [ORDERS]

問題概要

1~nまでの番号の兵士がバラバラに一列に並んでいる.
ソートするために,一番前の兵士から順番に,自分より大きな数字が前に居る限り1人ずつ追い越して行くという操作を繰り返した.
最初i番目にいた兵士はa[i]人だけ兵士を追い越した.
さて,最初に並んでいた順番を求める問題.
nは200000以下.

解法

一番最後の兵士は,1~nの番号の中で,a[n-1]番目に大きな数字.
同様に,後ろから見ていって,残っている番号の中で,a[k]番目に大きな数字が,k番目の兵士の番号.
これを高速に求めるために,Fenwick treeなどを使う.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1127-d46a9ecd
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。