SRM629 Div1 Easy "RectangleCovering"
考えたこと
穴の辺上に合わせるようにボードを乗っけることはできないと・・
つまりどういう事だってばよ
こう、縦横をテクニカルに埋めていって最小にする、みたいな事はできなそうだな!(フィーリング)
縦なら縦、横なら横、って感じで埋めてくしかなさそう。
辺の長いほうを埋めてくほうが有利かな?(フィーリング)
・・・最後のサンプル通らない
やっぱり縦と横両方やろ
通った!Submit!
撃 墜
あ、穴を埋めるのはちょうどでいいやん・・・辺上とか関係ないやん・・・
事後
今回通ったとしても、フィーリングでやるのはちょっとまずいよねぇ。考えが合ってるか多少なりとも証明するようにしないと・・・
ソースコード
class RectangleCovering { public: int minimumNumber(int holeH, int holeW, vector <int> boardH, vector <int> boardW) { int res = min(solve(holeH, holeW, boardH, boardW), solve(holeW, holeH, boardH, boardW)); if (res == 100) return -1; return res; } int solve(int a, int b, vector <int> boardH, vector <int> boardW) { int n = boardH.size(); vector<int> bs; for (int i = 0; i < n; i++) { int c1 = 0; int c2 = 0; if (a < boardH[i]) { c1 = boardW[i]; } if (a < boardW[i]) { c2 = boardH[i]; } bs.push_back(max(c1, c2)); } sort(bs.begin(), bs.end()); reverse(bs.begin(), bs.end()); int sum = 0; for (int i = 0; i <= n; i++) { if (sum >= b) return i; if (i == n) break; sum += bs[i]; } return 100; } };