AOJ 1188 (300)
AOJ-ICPC 3問目
大統領候補者が2人いて、投票で大統領を一人選出する。
各階層において過半数の地区で過半数の票数を得られた者が大統領に選出されるというルールの下、大統領に選出されるための最低得票数を求めるという問題。
括弧付きの計算機を作るのと少し似てるかな、でも階層構造は単純化されてるからこの問題の方が少し簡単かも。
＊解き方
入力を文字列Sとして受け取って、[ ]に囲まれた数字を1つの要素として考える。
P階層目の必要最低得票数は、P-1階層目の必要最低得票数を昇順ソートしたときの上位半分+1地区の必要最低得票数の和となる。
したがって、Sの要素が1個になるまで、Sを最初から最後までみるループを回し、P回目のループではP階層目の必要最低得票数Vを計算する。そして計算が終わったP階層目の要素を全部削除し、代わりにP+1階層目の要素としてVをSに入れて更新していくという方針で解いた。
ただし、入力で与えられるのは1階層目の地区の有権者数なので最初のループの計算方法に注意しなければいけない。
文章だと複雑になってうまく説明できないから、実装をみたほうが早いかな。
てか、めっちゃ時間かけちゃった
