Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2199-d6606bc1
この記事にトラックバックする(FC2ブログユーザー)

SRM531 DIV2 EASY - UnsortedSequence (この記事を編集する[管理者用])

Source

TopCoder SRM531 DIV2 EASY (250pt)
Problem Statement

問題概要

50要素以下の整数の配列が与えられる.(各要素は1以上1000以下)
順番を自由に入れ替えて,昇順ソートされていないような,辞書順最小のものを求める問題.
存在しないならそれを指摘する.

解法

sortしてから1回next_permutationする.
next_permutationしないなら,最後から見て,隣り合う値が違う最初の場所をスワップしてあげれば良い.
存在しないのは,すべての要素が同じ値の時.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

class UnsortedSequence {
public:
vector <int> getUnsorted(vector <int> s) {
  vector<int> em;
  sort(s.begin(), s.end());

  if(s[0]==s[s.size()-1]) return em;
  next_permutation(s.begin(), s.end());

  return s;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2199-d6606bc1
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。