SRM554 Div1 Medium(500) TheBrickTowerMediumDivOne

TheBrickTowerMediumDivOne

最初の塔と最後の塔の間隔が最小となるならば、最初の塔か最後の塔の少なくともどちらか一方は最長である。なぜならば、そうでなければ、両端の塔と最長の塔を交換することで、より間隔を小さくできてしまうから。最長の塔を最初か最後に持ってきて、それ以外の塔を再帰的に同様に並び替えることで、間隔を最小にできる。

#include <vector>
#include <algorithm>
using namespace std;

vector <int> H;
int n;

vector<int> solve( vector<bool> v )
{
    //  残っている最初の塔の添え字
    int f = find(v.begin(),v.end(),true)-v.begin();

    //  残っている塔が1個だけなら、その塔を返す
    if ( count(v.begin(),v.end(),true)==1 )
        return vector<int>(1,f);
    
    //  最長の塔
    int m = 0;
    for ( int i=0; i<n; i++ )
        if ( v[i] )
            m = max( m, H[i] );

    if ( H[f]==m )
    {
        //  残っている最初の塔が最長の塔ならば、その塔は最初のまま
        v[f] = false;
        vector<int> r = solve(v);
        r.insert(r.begin(),f);
        return r;
    }
    else
    {
        //  最長の塔のうち最後の塔を、最後に持ってくる
        int i = -1;
        for ( i=n-1; i>=0; i-- )
            if ( v[i] && H[i]==m )
                break;
        v[i] = false;
        vector<int> r = solve(v);
        r.push_back(i);
        return r;
    }
}

class TheBrickTowerMediumDivOne{public:
vector <int> find( vector <int> heights )
{
    H = heights;
    n = (int)H.size();
    return solve(vector<bool>(heights.size(),true));
}};