問題
http://yukicoder.me/problems/no/397
長さNの数列Aがある。
これに対して、u番目とv番目の要素を入れ替えるという操作をする。
数列の隣り合う3要素が門松列にならないようにするには、どのようにこの操作を行えばよいか。
門松列とは、3つの要素A1, A2, A3に対し、
- A1,A2,A3は全て異なる
- A2が最大か最小
3 <= N <= 100
1 <= Ai <= 100
考察
1. ある数列があり、門松列が含まれない数列を作るときは、どのようにすればよいか考える
2. すごく考える
3. ソートされた数列は門松列を含まない
4. なのでソートする感覚で入れ替え作業をしてやればいい
5. プロコンで出てくるソートは、バブルソートが一番良く出ると思ってる
6. バブルソートしてやる
実装
http://yukicoder.me/submissions/103932
int N; int A[100]; //----------------------------------------------------------------- int main() { cin >> N; rep(i, 0, N) cin >> A[i]; vector<pair<int, int> > ans; rep(i, 0, N) { int _max = i; rep(j, i + 1, N) if (A[_max] < A[j]) _max = j; if (_max != i) { ans.push_back(make_pair(i, _max)); swap(A[i], A[_max]); } } cout << ans.size() << endl; for (auto p : ans) printf("%d %d\n", p.first, p.second); int d; cin >> d; }