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)); }};