http://codeforces.com/contest/557/problem/C
n本の脚がついたテーブルがある。各脚の長さがL[i]で与えられる。このテーブルの脚を何本か切り落としてテーブルをStableな状態にしたい。テーブルがStableであるとは
・一番長い 脚の本数が残っている脚の中で過半数を占めている
ということを指す。また、脚が1本だけのテーブルはStableであるとする。
テーブルの各脚を切り落とすにはコストが必要でそれぞれのコストがd[i]で与えられる。
Stableにするための最小コストを求めよ。
制約としてn<=10^5, L[i]<=10^5, 1<=d[i]<=200
解法
脚の長さでソートしたあと、最長の脚をL[i]にした時の最小コストというのを各iについて求めれば良い。
最長の脚をL[i]にした時の最小コストというのは、
1. L[i]より長い脚を全て切る
2. L[i]より短い脚を、L[i]の脚が過半数になるようにコストが小さい順に切っていく
ことによって得られる。
1はコストの累積和をあらかじめ計算しておけば簡単に求められる。
2は今脚L[i]をみている時に、それまでみていた脚の中でコストjの脚が何本あるかというヒストグラムを保持しておけば高速に求められる(d[i]が200以下であるため)
0 件のコメント:
コメントを投稿