Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Timus 1998 - The old Padawan (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1998

問題概要

$n$ 個の石の重さ $w_1,w_2,\ldots,w_n$ が与えられる.
これらの石を順番に空中に浮かすお仕事を行う.
$1$ 秒ごとに $1$ 個の石を空中に浮かべることができる.(まだ浮かべていないうち,番号の若い石から浮かべていく)
ただし,悪友が $m$ 回邪魔してくる.
邪魔してくるタイミングはわかっており, $t_1, t_2, \ldots, t_m$ 秒目に邪魔してくる.
邪魔されると,その秒は石を浮かべることができず,更に,浮かべた石のうち新しい方から
 落とした石の重さが $k$ を厳密に超えるまで(もしくは浮かんでいる石がなくなるまで)
石が落とされる.
全ての石を浮かべるまでにかかる時間を求める問題.
全ての邪魔が行われる前に浮かべ終わることもある.
$1 \leq n, m \leq 10^5$
$1 \leq w_i \leq 10^4$
$1 \leq k \leq 10^9$
$1 \leq t_1 < t_2 \cdots t_m \leq 10^9$ $(t_i < t_{i+1})$

解法

まず,どの段階で邪魔されたらいくつ石が落とされるかをしゃくとりメソッドか二分探索などを用いて求めておく.
後は,イベントが起こるまでの時間を端折りつつシミュレーションすれば良い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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