Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Timus 1995 - Illegal spices (この記事を編集する[管理者用])

Source

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

問題概要

$n$ 個の荷物があって,順番に重さを量る.
それぞれの荷物の重さ $w_i$ は正整数.
$2$ 個目以降の荷物は,今まで量った荷物で,より軽いものの割合が $p$ %以上あるなら破棄する.
破棄された荷物の数はちょうど $k$ 個であった.
$n,k,p$が与えられるので,重さの総和の最小値と,それを満たす $w_1,w_2,\ldots,w_n$ を $1$ つ求める問題.
$1 \leq k < n \leq 10^5$
$1 \leq p \leq 100$

解法

最初 $n-k$ 個の荷物は全部重さを $1$ にして,最後の $k$ 個は
 前の荷物と同じ重さで破棄されるなら,そうする
 そうでなければ,前の荷物の重さ + 1
とすれば良い.
重さの総和は32ビットに収まらないことに注意.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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