ハッカーランキング-Lily's Home work

リリーの宿題を手伝わなければなりません.
作業内容は以下の通りです.
任意のサイズnの配列では、n未満のiに対して
|arr[i]-arr[i-1]|の和が最小です.
再配置時に変更できるのは、2つの要素の値だけです.(交換)
このとき必要な交換回数が最も少ないという問題がある.
解題ポリシー
|arr[i]-arr[i-1]|の和を最小にするには、配列を整列させる必要があります.
これは、ソート時に必要な交換回数を求めることができる問題です.
重要な点は、昇順で作成する回数と降順で作成する回数が異なるため、どちらの場合もより小さな値を返す必要があります.
スイッチを用いてソートするには,毎回最大(最小)値を要求し,先にスイッチを開始した選択ソートを用いる.
この場合,与えられる配列長は10^5に制限され,従来の選択ソートでは解決できない.(O(n^2))
Mapデータ構造を利用して,最大(最小)値を探す際にO(n)を必要とする選択ソートを見つければ,O(logn)で解決できる.
すなわち,Mapを使えばO(nlogn)を使って問題を解決できる.
解答順は以下の通りです.

は、最初に、昇順と降順の2つのMapを宣言する.
1.1. Mapでは、ストレージ数とインデックスを許可します.

修正する2つの配列を作成し、値をコピーして挿入します.

の場合、いずれの場合もMapは巡回され、可能な位置でなければ2つの位置が交換されます.
3.1. このとき交換後mapのvalueも更新されます.

で得られた2つの値のうち、より小さい値が返される.

コード#コード#

int lilysHomework(vector<int> arr) {
    vector<int> arr2;
    for(int i=0;i<arr.size();i++){
        arr2.push_back(arr[i]);
    }
    map<int, int> m;
    map<int, int> mm;
    for(int i=0;i<arr.size();i++){
        m.insert(make_pair(arr[i],i));
        mm.insert(make_pair(-arr[i],i));
    }
    
    int idx = 0;
    int cnt = 0;
    for(auto iter = m.begin();iter != m.end();iter++){
        if(iter->second == idx){
            idx++;
            continue;
        }
        int tmp = arr[idx];
        arr[iter->second] = arr[idx];
        arr[idx] = iter->first;
        m[tmp] = iter->second;
        idx++;
        cnt++;
    }
    int id = 0;
    int ct = 0;
    for(auto iter = mm.begin();iter != mm.end();iter++){
        if(iter->second == id){
            id++;
            continue;
        }
        int tmp = -arr2[id];
        arr2[iter->second] = arr2[id];
        arr2[id] = -iter->first;
        mm[tmp] = iter->second;
        id++;
        ct++;
    }
    return min(cnt,ct);
}

ソース
https://www.hackerrank.com/challenges/lilys-homework/problem?isFullScreen=true