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


題目描述

這天是新年的第一天,所有人都在遊樂園排隊等著玩雲霄飛車。在排隊中的每個人,身上都會貼著一張貼紙,上面的數字為他們一開始的位置,排在最前面的數字為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/

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章