[HackerRank]新年的混亂(New Year Chaos)

題目描述

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

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

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

原題網址

輸入格式

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

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

輸出格式

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

範例輸入

範例輸出

額外解釋

測試資料一：

5和4交換：

5和3交換：

2和1交換：

一共換了3次。

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

解題概念

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

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

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

參考答案

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