HackerRank New Year Chaos(Algorithms>Implementation)

題目:
新年到了，大家都在排Wonderland的雲霄飛車!
(OS:新年和雲霄飛車到底啥關係=口=)
有n個人在排隊，每個人都會貼上一個貼紙，
用來代表他們原本在隊列中最初的位置。
(例:1, 2, 3, ..., n-1, n，最前面的人編號是1，以此類推)

任何一個人都可以透過賄賂和自己前面的那一個人交換位置。
(只能跟剛好現在在自己前面的，也就是5可以跟4換，但不可以跟3換)
換完位置以後他們身上的貼紙維持原樣，不會跟著交換。
每個人最多只能賄賂兩次，不能再多XD

當你到現場時，只看到最後的隊列長成現在這個樣子，
而你決定你要知道將隊列變成現在這樣子，
所需的最小次數的總賄賂次數是多少。
(別隨便幫我決定阿喂!!!!!)

輸入:
第一行輸入T，代表總數的測資(test cases).
每筆測資由2行組成，第一行為隊列人數n，
第二行則列出最終的隊列排列的樣子(n個數字，由空格隔開)。
限制為1<=T<=10, 1<=n<=10的5次方。

輸出:
如果沒辦法透過每人2次以內的賄賂達到測資要求的狀況，
就印出Too chaotic，
否則則印出最小所需的賄賂次數。

例:
輸入

2
5
2 1 5 3 4
5
2 5 1 3 4

輸出

3
Too chaotic

解題:
這也是Medium Level的題目，
我覺得我的解法並沒有能夠完整證明答案的可靠度，
但基本上應該沒錯，如果有有興趣的讀者或大神，
或許可以幫忙看看要怎麼樣才能更嚴謹地將解題部分證明更詳細些。

我們怎麼檢查這個隊列是否是有解的呢?
其實只要檢查每個人的位置離起始位置是否超過2單位的距離。
因為每個人都只能賄賂2次，
如果那個位置距離你3格以上(比如原本在4，想到1的位置)，
那勢必要賄賂3次以上才行，因為沒有人會跟你賄賂交換後面的位置XD
那麼如果所有人都離自己目標2格以內的話(指後-前= 正2以內)，
從第一個位置開始，讓想到該位置的人開始賄賂排到那個位置，
我們可以排好i=1, 2, 3, ..., n-1的所有人，於是i=n的人也會是剛好的那個人。
(因為前面都排好了)

而且從最前面開始排的話，最前面的人的賄賂次數不會浪費，
因為一排到那邊去接下來就鎖定不動了，故這個排列方式也是花費最少的次數。

在code中為了要實作，
我們定義以下幾個變數和陣列:
bribe_total -> 總賄賂次數
temp -> 交換用
chao -> 是否無法達成此狀態
q_now -> 目前的隊列排列狀態
pos_now -> 編號i+1的人目前所在的位置
q -> 測資給入的最終隊列狀態。

首先輸入q以後，我們可以同步藉由此迴圈，
將q_now和pos_now給輸入完成。
接下來先檢查每個距離差是否>2，
是的話就直接讓chao=1且後面輸出Too chaotic，
否則後面才繼續做。

接下來透過迴圈計算每項的diff(距離差)，
diff為2的話，
表示那個人要賄賂兩次，
比如:

1 2 3 -> 3 1 2

編號3的人賄賂了2次，
於是前移2單位，中間的人則各自後移2單位，
依此更新陣列狀態並將bribe_total加2。

diff為1的話，
則前後交換，更新陣列狀態並將bribe_total加1。

持續從i=0做到i=n-2，
將0~n-1給排好，即可得到總賄賂次數，
並將其印出。

Code：

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int T; 
    scanf("%d",&T);
    for(int a0 = 0; a0 < T; a0++){
        int n, bribe_total = 0, chao = 0; 
        scanf("%d",&n);
        int *q = malloc(sizeof(int) * n);
        int q_now[n], pos_now[n];
        for(int q_i = 0; q_i < n; q_i++){
            scanf("%d",&q[q_i]);
            q_now[q_i] = q_i + 1;
            pos_now[q_i] = q_i;
        }
        for(int i = 0; i < n; i++){
            if(pos_now[q[i]-1] - i > 2)
            {
                chao = 1;
                break;
            }
        }
        if(chao){
            printf("Too chaotic\n");
        }else{
            for(int i = 0; i < n-1; i++)
            {
                int temp = q[i], diff = pos_now[q[i]-1] - i;
                if( diff == 2 )
                {
                    bribe_total +=2;
                    pos_now[q_now[i+1]-1]++;
                    pos_now[q_now[i]-1]++;
                    pos_now[q_now[i+2]-1] -= 2;
                    q_now[i+2] = q_now[i+1];
                    q_now[i+1] = q_now[i];
                    q_now[i] = temp;
                } else if( diff == 1 ){
                    bribe_total++;
                    pos_now[q_now[i]-1]++;
                    pos_now[q_now[i+1]-1]--;
                    q_now[i+1] = q_now[i];
                    q_now[i] = temp;                    
                }                    
            }    
            printf("%d\n", bribe_total);
        }
    }
    return 0;
}