## Problem
莫伊斯特 (Moist) 有一個愛好：收集花式滑冰收藏卡。他收集的卡片越來越多，到現在已經多到無法隨便堆在一疊了。莫伊斯特需要把卡片上的人名以字母順序排序，以便在需要的時候能夠迅速的找到他要的卡片。
但問題來了：莫伊斯特無法拿起卡片，因為它們出於某些因素一直從他的手中滑落，且手上的汗水亦會對卡片造成永久性傷害。要知道，有些卡片可是非常昂貴的。因此，為了避免傷害到他寶貴的卡片，莫伊斯特說服了糟糕博士 (Dr. Horrible) 為他設計了一個排序機器人。然而，以糟糕博士十分糟糕的風格，他決定讓機器人在每次移動卡片的時候向莫伊斯特收取 $1 的手續費。
經過一段時間的觀察，莫伊斯特發現機器人的排序方式非常的原始：它從上至下掃描整堆卡牌，且每當它發現某一張卡片在字母順序上小於它上面一張卡片時，就會將該卡片移動至上方卡堆中的正確位置，此操作會花費 $1。它會像這樣不斷的往卡堆的底部掃描，一張一張的移動卡牌，如此一來當掃描到最後一張結束時，便完成了對整堆卡牌的排序。
然而時運不濟的莫伊斯特早已瀕臨破產，而維持收藏卡的井然有序是他悲慘的人生中唯一剩下的快樂。因此他想要知道使用機器人對他的卡牌進行排序總共需要花費多少錢。
## Input
輸入的第一行有一個正整數 **T** 表示測資數量。緊接著會有 **T** 筆測資。每筆測資的第一行均有一個正整數 **N** 表示卡片數量。接下來會有 **N** 行，每行代表一張卡片，且含有一位花式滑冰選手的名字。卡片依照卡堆從頂部至底部的順序輸入。
## Output
對每筆測資，均印出一行格式為 `Case #x: y` 的字串，而其中的 `x` 為測資編號 (從 1 開始)，`y` 表示莫伊斯特使用機器人對他的卡牌進行排序總共需要花費的金額。
## Limits
時間限制：每一測資組 60 秒。
記憶體限制：1 GB。
$1 \le$ **T** $\le 100$。
名字均只含英文字母與空白字元。
名字的長度不超過 100 個字元。
名字均不會以空白字元開頭或結尾。
同一筆測資內不會出現重複的名字。
字母順序為空格優先，接著是大寫英文字母與小寫英文字母。
### Small dataset
$1 \le$ **N** $\le 10$。
### Large dataset
$1 \le$ **N** $\le 100$。
## Sample
#### Sample Input
```
2
2
Oksana Baiul
Michelle Kwan
3
Elvis Stojko
Evgeni Plushenko
Kristi Yamaguchi
```
#### Sample Output
```
Case #1: 1
Case #2: 0
```
---
在第一筆測資中，只需將 `Michelle Kwan` 移至 `Oksana Baiul` 上方即可，共需一次操作，故輸出 `1`。
在第二筆測資中，由於所有卡牌均已照字母順序排序，故不需任何操作，輸出 `0`。
## Datasets
#### Small dataset
* [Input Raw](https://github.com/google/coding-competitions-archive/raw/main/kickstart/2013/practice_round/moist/data/secret/subtask1/1.in)
* [Output Raw](https://github.com/google/coding-competitions-archive/raw/main/kickstart/2013/practice_round/moist/data/secret/subtask1/1.ans)
#### Large dataset
* [Input Raw](https://github.com/google/coding-competitions-archive/raw/main/kickstart/2013/practice_round/moist/data/secret/subtask2/1.in)
* [Output Raw](https://github.com/google/coding-competitions-archive/raw/main/kickstart/2013/practice_round/moist/data/secret/subtask2/1.ans)
## Solution
:::spoiler Editorial (C++11)
---
### Algorithm
本題是一個經典排序問題，若不謹慎思考可能會大費周章的按照題目敘述進行模擬，然而這麼做不僅沒有必要性，還會浪費時間與記憶體空間。
題目敘述指出，機器人是透過向下遍歷整堆卡牌來比較排序，透過比較當前卡牌與其上方卡牌的大小，將當前卡牌移動至上方已嚴謹排序的卡堆內的正確位置。但我們不必真的去實作這一點，只需要「假裝」該卡牌已被移動且排序即可。
我們可以透過**雙指針 (two pointer)** 來實作這一點。第一個指針紀錄當前卡牌，第二個指針紀錄第一個指針的「理論上方卡牌」。注意到第一個指針並不一定會和題目所述的一樣緊貼第二個指針，因為我們其實沒有去實作「移動」這個步驟。因此雙指針之間可能存在其他卡牌，而這些其實是已被「假裝移至上方卡堆」的卡牌。
我們讓第一個指針如同題目所述的向下遍歷整堆卡牌，而第二個指針負責記錄最大字母順序之卡牌。且每當第一個指針之卡牌字母順序比第二個指針之卡牌小時，代表需要進行「移動」，便將所需花費增加一，然而如同上述，我們並不需要去真正的「移動」它。
如此不斷重複直至第一個指針遍歷完成，即結束此排序模擬。
### Implementation
#### Step 1: 編寫基本框架
為了使用 C++ 的標準函式庫，需要引入 `stdc++.h` 標頭檔：
```cpp=
#include <bits/stdc++.h>
```
為了更加快速的使用 `std` 命名空間，加入以下程式：
```cpp=
using namespace std;
```
接著定義 `main` 函式內容：
```cpp=
int main() {}
```
於 `main` 函式中加入輸入輸出優化：
```cpp=
ios::sync_with_stdio(false);
cin.tie(nullptr);
```
##### Step 1 程式
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
```
#### Step 2: 處理輸入資料
讀取輸入之測資數量 **T** 於 `case_cnt`：
```cpp=
int case_cnt;
cin >> case_cnt;
```
對每筆測資，讀取輸入之卡牌數量 **N** 於 `card_cnt`：
```cpp=
int card_cnt;
```
```cpp=
for (int i = 0; i < case_cnt; ++i) {
cin >> card_cnt;
}
```
為了節省記憶體空間與運算時間，我們讓讀取輸入之人名與雙指針模擬排序同步進行，因此對剩餘輸入資料的處理將移至演算法內。
##### Step 2 程式
```cpp=
#include <bits/stdc++.h>
using namespace std;
int card_cnt;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int case_cnt;
cin >> case_cnt;
for (int i = 0; i < case_cnt; ++i) {
cin >> card_cnt;
}
}
```
#### Step 3: 編寫演算法
創建一函式 `solve` 回傳一整數作為答案：
```cpp=
int solve() {}
```
於 `main` 函式中輸出答案：
```cpp=
cout << "Case #" << i + 1 << ": " << solve() << '\n';
```
於 `solve` 函式內創建一整數 `cost` 用以儲存總花費：
```cpp=
int cost = 0;
```
創建**雙指針**字串 `curr_name`, `last_name`：
```cpp=
string curr_name, last_name;
```
接著準備讀取輸入之人名，而此時題目要求讀取整行含空格之字串，因此不能使用 `>>` 運算子讀取。此時須改為使用 `getline()` 來讀取整行字串。但在使用 `getline()` 之前，由於我們先前已使用了 `>>` 運算子讀取了 `card_cnt`，會有一個額外換行字元，因此要先將該換行字元讀掉，才能開始讀取輸入。
讀掉換行字元：
```cpp=
getline(cin, curr_name);
```
讀取輸入之人名於第一指針 `curr_name`：
```cpp=
for (int i = 0; i < card_cnt; ++i) {
getline(cin, curr_name);
}
```
此時若為第一筆輸入，則須更新 `last_name`：
```cpp=
if (last_name.empty()) {
last_name = curr_name;
continue;
}
```
否則判斷 `curr_name` 和 `last_name` 的字母順序，若 `curr_name` 的字母順序小於 `last_name` 即表示需要進行一次移動，要將 `cost` 增加一；否則更新比較對象 `last_name` 的值：
```cpp=
if (curr_name.compare(last_name) > 0) {
last_name = curr_name;
} else {
++cost;
}
```
其中的 `compare` 函式可用於比較兩字串的字母排序，若呼叫字串排序於參數字串之前則輸出 $< 0$；兩字串排序相同則輸出 $0$；否則輸出 $> 0$。
輸入讀取結束時亦同時完成排序，此時輸出總花費 `cost`：
```cpp=
return cost;
```
##### solve 函式內容
```cpp=
int solve() {
int cost = 0;
string curr_name, last_name;
getline(cin, curr_name);
for (int i = 0; i < card_cnt; ++i) {
getline(cin, curr_name);
if (last_name.empty() || curr_name.compare(last_name) > 0) {
last_name = curr_name;
} else {
++cost;
}
}
return cost;
}
```
---
#### Full Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int card_cnt;
int solve() {
int cost = 0;
string curr_name, last_name;
getline(cin, curr_name);
for (int i = 0; i < card_cnt; ++i) {
getline(cin, curr_name);
if (last_name.empty() || curr_name.compare(last_name) > 0) {
last_name = curr_name;
} else {
++cost;
}
}
return cost;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int case_cnt;
cin >> case_cnt;
for (int i = 0; i < case_cnt; ++i) {
cin >> card_cnt;
cout << "Case #" << i + 1 << ": " << solve() << '\n';
}
}
```
### Complexity Analysis
#### 總時間複雜度：$O(TN)$
* `Line 29-32`：$t(T) = O(T)$，因從 `0` 開始遍歷至 `case_cnt - 1`。
* `solve()`：$t(N) = O(N)$，因演算法遍歷所有輸入卡牌一次。
總時間複雜度：$t(T, N) = O(TN)$。
#### 額外時間複雜度：$O(1)$
額外時間複雜度表演算法在對整理後的輸入資料進行計算所需的時間複雜度，而本題之資料處理與輸入讀取為同時進行，故額外時間複雜度為 $O(1)$
#### 總空間複雜度：$O(1)$
#### 額外空間複雜度：$O(1)$
:::
## Notes
1. 題目的背景設定來源於 2008 年的一部音樂迷你劇《糟糕博士的歡唱部落格》(Dr. Horrible's Sing-Along Blog)，此音樂劇在當時獲得了很大的反響，也榮獲了多項獎項，如最佳網絡劇觀眾選擇獎、最佳喜劇網絡劇導演獎、最佳喜劇網絡劇編劇獎、最佳喜劇網絡劇男演員 (哈里斯) 獎、最佳剪輯、最佳攝影和最佳原創音樂獎。
## References
1. https://github.com/google/coding-competitions-archive/blob/main/kickstart/2013/practice_round/moist/statement.pdf
2. https://en.wikipedia.org/wiki/Dr._Horrible%27s_Sing-Along_Blog
Sign in with Wallet
Connect another wallet