NO MORE KADOMATSU [yukicoder 397]

問題

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