550ptということでDiv2 Mediumにしてはちょっと難しめ。
http://community.topcoder.com/stat?c=problem_statement&pm=13340
問題
N人の生徒がそれぞれC[i]の容積の入れ物を持っており、W[i]の重さの飴を欲しがっている。
各生徒の容器に、ある密度の飴を入れることを考える。
この時、各生徒の不幸は入れ物いっぱいに入れた飴の重さとW[i]の差の絶対値となる。
不幸の総和が最小となるよう、密度を決めよ。
解法
密度をWとすると、不幸の総和はである。
個々の|x*C_i - W_i|は明らかに下に凸なので、それを重ねた上記総和も下に凸である。
よってWを三分探索で求めればよい。
class CandyMaking { public: int N; vector<int> V1,V2; double diff(double den) { double tot=0; int i; FOR(i,N) tot+=fabs(V2[i]-V1[i]*den); return tot; } double findSuitableDensity(vector <int> containerVolume, vector <int> desiredWeight) { N=containerVolume.size(); V1=containerVolume; V2=desiredWeight; double L=1e9,R=1e-9; int i; FOR(i,N) L=min(L,1.0*V2[i]/V1[i]); FOR(i,N) R=max(R,1.0*V2[i]/V1[i]); FOR(i,100) { double M1=(L*2+R)/3; double M2=(L+R*2)/3; double D1=diff(M1),D2=diff(M2); if(D1<D2) R=M2; else if(D1>D2) L=M1; else L=M1,R=M2; } return diff((L+R)/2); } }
まとめ
三分探索だから550ptなんだろうね。