題目描述

這天是新年的第一天,所有人都在遊樂園排隊等著玩雲霄飛車。在排隊中的每個人,身上都會貼著一張貼紙,上面的數字為他們一開始的位置,排在最前面的數字為1,排在第二位置的數字為2,排在最後第n位置的數字為n。任何在這個排列隊伍中的人,都可以賄賂排在前面的人,並與前面的人交換位置,但不交換貼紙。每個人最多可以賄賂其他人兩次。



舉例來說,若有8個人排隊,一開始,若在第五位置的人賄賂了第四位置的人,則在他們交換位置後,隊伍的排列情形如下:

1 2 3 5 4 6 7 8

透過的這個混亂的排隊規矩,您必須要計算出若要從最原先的順序排成目前的順序,共最少需要多少的賄賂次數才可達成。

原題網址

https://www.hackerrank.com/challenges/new-year-chaos

輸入格式

輸入第一行為一個整數,表示測試資料的數量,範圍在1到10之間(包含1和10)。

每個測試資料由兩行組成。第一行為排隊的人數,範圍在1到105之間(包含1和105)。第二行為目前隊伍排列的情形,以最初獲得的貼紙數字表示,用空格分隔。

輸出格式

輸出最少需要多少的賄賂次數才可從最初的順序換成目前的順序。如果沒有辦法換成目前的順序,輸出「Too chaotic」

範例輸入

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

範例輸出

3
Too chaotic

額外解釋

測試資料一:

1 2 3 4 5

5和4交換:

1 2 3 5 4

5和3交換:

1 2 5 3 4

2和1交換:

2 1 5 3 4

一共換了3次。

測試資料二沒有任何方法可以將原本的排列換成目前的排列。

解題概念

先實作出Person類別,來模擬排隊者的行為。首先每個排隊者都會有個固定的貼紙,上面的數字表示為自己一開始排隊的位置,所以有個不會被改變數值的「firstPosition」欄位。接著每個排隊者都有各自的剩餘賄賂次數,用「bribesChance」欄位來儲存。實作出bribes方法,如果賄賂成功,將bribesChance欄位的值減一,並回傳true;如果賄賂失敗,回傳false。

有了Person類別後,可以先將測試資料的隊伍使用Person來模擬。接著我們已知每位排隊者只能向前插隊,且只能夠行使兩次的賄賂,所以我們可以知道,不管有沒有被其他排隊者插隊,一個排隊者目前的位置絕對不會超過原本排隊位置之前兩個位置,所以原本位置減掉目前位置的最大值為2。

從隊伍最前面開始,逐一計算所有排隊者前進或是後退的距離,若有人前進的位置超過2,則此隊伍必定不是按照題目的規定方式來賄賂插隊。如果發現到有人不是在之前的位置上的話,則開始還原其至原本的位置上,這個動作有點像是氣泡排序法,先將最小值擠回到前面的位置,只是每個元素的移動次數會有所限制。有關於氣泡排序法的說明可以參考這篇文章:

https://magiclen.org/sorting-algorithm/

參考答案

import java.util.Scanner;

public class Solution {

    public static void main(final String[] args) {
        final Scanner sc = new Scanner(System.in);

        int T = Integer.parseInt(sc.nextLine());
        while (T-- > 0) {
            final int n = sc.nextInt();
            final Person[] a = new Person[n];
            for (int i = 0; i < n; ++i) {
                a[i] = new Person(sc.nextInt());
            }

            final int n_dec = n - 1;
            int counter = 0;
            RECOVER:
            for (int i = 0; i < n_dec; ++i) {
                final int d = a[i].firstPosition - i;
                if (d > 3) {
                    counter = -1;
                    break;
                } else if (d != 1) {
                    for (int j = n_dec - 1; j >= i; --j) {
                        if (a[j].firstPosition > a[j + 1].firstPosition) {
                            if (!a[j].bribes()) {
                                counter = -1;
                                break RECOVER;
                            }
                            final Person temp = a[j];
                            a[j] = a[j + 1];
                            a[j + 1] = temp;
                            ++counter;
                        }
                    }
                }
            }
            System.out.println(counter > -1 ? counter : "Too chaotic");
        }
    }
}

class Person {

    final int firstPosition;
    private int bribesChance = 2;

    Person(final int finalPosition) {
        this.firstPosition = finalPosition;
    }

    boolean bribes() {
        if (bribesChance == 0) {
            return false;
        }
        --bribesChance;
        return true;
    }

    @Override
    public String toString() {
        return String.valueOf(firstPosition);
    }
}