2014年9月20日 星期六

2014/9/20 TopCoder SRM 629 Div1 250 RectangleCovering

/*
    vector 也能 assign 和 swap 噢 >.O 
*/
// http://community.topcoder.com/stat?c=problem_statement&pm=13344&rd=16060
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int H, W;
vector<int> bH, bW;

bool cmp(int a, int b)
{
    if( bH[a] > H && bH[b] <= H ) return true;
    if( bH[a] > H && bH[b] > H && bW[a] > bW[b] ) return true;
    return false;
}

int sp[100];

struct RectangleCovering
{
    int minimumNumber(int _H, int _W, vector <int> _bH, vector <int> _bW)
    {
        int Ans = -1;

        H = _H; W = _W; bH = _bH; bW = _bW;
        int n = bH.size();

        for(int j = 0; j < 2; j++)
        {

            for(int i = 0; i < n; i++)
            {
                sp[i] = i;
                if( bW[i] > H && ( bW[i] < bH[i] || bH[i] <= H )  ) 
                    swap(bW[i], bH[i]);
            }

            sort(sp, sp+n, cmp);

            int sum = 0;

            for(int _i = 0; _i < n; _i++)
            {
                int i = sp[_i];
                if( bH[i] > H ) sum += bW[i];
                if( sum >= W )
                {
                    if( Ans == -1 ) Ans = _i+1;
                    else Ans = min(Ans, _i+1);
                }
            }

            swap(W, H);
            swap(bW, bH);
        }

        return Ans;
    }
};

沒有留言:

張貼留言