SRM461 Div1 Easy(300), Div2 Medium(550) ColoringRectangle

ColoringRectangle

大きい順で赤青交互に並べていく。赤から始める場合と青から始める場合の両方試す。

#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

class ColoringRectangle
{
    int choose( int width, int height, vector<int> d1, vector<int> d2 );
public:
    int chooseDisks( int width, int height, vector <int> red, vector <int> blue );
};

int ColoringRectangle::chooseDisks( int width, int height, vector <int> red, vector <int> blue )
{
    int n1 = choose( width, height, red, blue );
    int n2 = choose( width, height, blue, red );

    if ( n1 == -1 )
        return n2;
    if ( n2 == -1 )
        return n1;
    return min( n1, n2 );
}

int ColoringRectangle::choose( int width, int height, vector<int> d1, vector<int> d2 )
{
    //  d1, d2のうちheight以上のディスクを降順に交互に並べる
    vector<int> disk;

    sort( d1.begin(), d1.end() );
    sort( d2.begin(), d2.end() );

    while ( true )
    {
        if ( d1.empty()  ||  d1.back() < height )
            break;
        disk.push_back( d1.back() );
        d1.pop_back();
        
        if ( d2.empty()  ||  d2.back() < height )
            break;
        disk.push_back( d2.back() );
        d2.pop_back();
    }

    //  置いていく
    double x = 0;   //  最後のディスクと長方形の接点（右側）
    int c = 0;      //  置いたディスクの数

    while ( true )
    {
        if ( x >= width )
            return c;

        if ( c >= (int)disk.size() )
            return -1;

        x += sqrt( (double)( disk[c]*disk[c] - height*height ) );
        c++;
    }
}