TopCoder SRM629 DIV1 EASY - RectangleCovering

Source

TopCoder SRM629 DIV1 EASY (250pt)
Problem Statement

問題概要

地面に縦 $H$,横 $W$ のサイズの穴が空いている.
また,$N$ 個の長方形の板があり,板 $k$ のサイズは $X_k \times Y_k$ である.
板で穴を塞ぎたいのだけど,最小で何個の板で穴を完全に塞げるか求める問題.
板の各辺は,穴の各辺に平行に置かなくてはいけなくて,板の任意の頂点は穴の中,または,穴の辺上にあってはいけない.
板は90度回転しても良い.板は重なってても良い.

解法

全ての頂点は穴の上にあってはいけないので,橋渡しのように,穴を横切るように板を置くしかない.
縦,横,どちらに横切るように置くかは両方試す.
各板は,横切るようにおける向きで,できるだけ幅を稼げる向きに置く.
稼げる幅の大きい方から貪欲に使えば良い.
等号,不等号周りに注意.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define INF 1000000000

class RectangleCovering {
public:
int minimumNumber(int X, int Y, vector <int> bX, vector <int> bY) {
  int i, j, k, loop, N;
  int arr[100], sz;
  int res = INF;

  N = bX.size();

  rep(loop, 2){
    sz = 0;
    rep(i,N){
           if(min(bX[i], bY[i]) > X) arr[sz++] = max(bX[i], bY[i]);
      else if(max(bX[i], bY[i]) > X) arr[sz++] = min(bX[i], bY[i]);
    }
    sort(arr, arr+sz); reverse(arr, arr+sz);

    k = 0;
    rep(i,sz){
      k += arr[i];
      if(k >= Y){ res = min(res, i+1); break; }
    }
    
    swap(X, Y);
  }

  if(res == INF) res = -1;

  return res;
}

}

Current time: 2017年11月18日04時24分41秒
Last modified: 2014年08月13日03時48分14秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM629 SRM_Div1_Easy
トップページに戻る

Logged in as: unknown user (not login)

ログイン: