読者です 読者をやめる 読者になる 読者になる

SRM 673 Div2 Medium BearSlowlySorts

問題

SRM 673 - TopCoder Wiki

要素Nの配列をソートする,今N-1個の連続する要素は1回の操作でソート可能. 全体の配列をソートするのに必要な最小の操作回数を求める問題.

解答

パターン分けをすると幾つかの場合が考えられる.

  • 既にソートされている.操作回数0
  • 最小値が一番左 or 最大値が一番右.操作回数1
  • 最大値が一番左 and 最小値が一番右.操作回数3
  • それ以外.操作回数2
class BearSlowlySorts
{
public:
  int minMoves(vector <int> w)
    {
      vector<int> dummy = w;
      int n = w.size();
      sort(dummy.begin(), dummy.end());
      bool minleft = dummy[0] != dummy[1] && dummy[0] == w[0];
      bool minright = dummy[0] != dummy[1] && dummy[0] == w[n-1];
      bool maxright = dummy[n-1] != dummy[n-2] && dummy[n-1] == w[n-1];
      bool maxleft = dummy[n-1] != dummy[n-2] && dummy[n-1] == w[0];
      cout << minleft << minright  << maxleft << maxright << endl;
      if (dummy == w) return 0;
      if (minleft || maxright) return 1;
      if (minright && maxleft) return 3;
      return 2;
    }
};