SRM461 Div1Easy ColoringRectangle
解法
直径を大きい順にソートして(1)r,b,r,b,... or (2)b,r,b,r,...の順で貪欲でつめる。red or blue の要素で直径が H 以上のものが尽きたら -1 を出力。そうでなければ長方形の残りの幅を越えた時点で最適。(1)と(2)の小さい方が答え。
class ColoringRectangle { public: int chooseDisks( int width, int height, vector <int> red, vector <int> blue ) { sort(ALL(red), greater<int>()); sort(ALL(blue), greater<int>()); double const H = height; int ans = red.size()+blue.size()+10; for(int s=0; s<2; s++) { double remain = width; int flag = s; int rcnt = 0, bcnt = 0; while(remain > 1e-5) { double d; if(flag==0) { if(rcnt < (int)red.size()) { d = red[rcnt++]; if(d < H) goto NEXT; } else goto NEXT; } else { if(bcnt < (int)blue.size()) { d = blue[bcnt++]; if(d < H) goto NEXT; } else goto NEXT; } remain -= 2.*sqrt(SQ(d/2) - SQ(H/2)); flag = !flag; } ans = min(ans, rcnt+bcnt); NEXT:; } if(ans > int(red.size()+blue.size())) return -1; return ans; } };