大神的世界

想法很簡單，就是將 sort 好的位置與原位置相減取絕對值

相加後即為最短距離

但要注意使用的 sort 必須 stable ，也就是 selection sort 、heap sort 和 quick sort 不行

因此如果使用內建的 sort 函數會出問題 

因為我懶的寫 merge sort 所以效率比較差 ( 我使用 bubble sort ) 

#include <iostream>
#include <cmath>

using namespace std;

constexpr int MAX_STATUS_NUM = 10000;

struct status{
    int id;
    int height;
    int weight;
};

bool cmp(const status &_a, const status &_b)
{
    return _a.height < _b.height || ((_a.height == _b.height) && (_a.weight <= _b.weight));
}

int main()
{
    int status_num;
    while(cin >> status_num){
        status st[MAX_STATUS_NUM];
        for(int i = 0; i<status_num; i+=1){
            cin >> st[i].height >> st[i].weight;
            st[i].id = i;
        }

        for(int i = 0; i<status_num; i+=1){
            for(int j = 0; j<status_num-i-1; j+=1){
                if(!cmp(st[j], st[j+1]))
                    swap(st[j], st[j+1]);
            }
        }

        int sum = 0;
        for(int i = 0; i<status_num; i+=1){
            sum += abs(st[i].id - i);
        }

        cout << sum << endl;
    }

    return 0;
}