博物館的展間有 N 座雕像，分別放在位置 1、2、…、N，已知放在位置 i 的雕像重量為 W。i 管理員要依照雕像的重量對它們排序：如果存在兩座相鄰的雕像，也就是分別在位置 i 和 i+1，滿足 Wi > Wi + 1，管理員會以機器交換兩座雕像的位置，此一動作會花費 Wi + Wi + 1 單位的電力。
管理員會重複前述的交換動作，直到所有雕像依重量由小到大排序。
例如：有 N = 3 座重量不同的雕像，(W1, W2, W3) = (5, 7, 4)。首先交換位置 2 和 3 的雕像，花費 7 + 4 = 11 單位的電力，此時 (W1, W2, W3) = (5, 4, 7)。接著交換位置 1 和 2 的雕像，花費 5 + 4 = 9 單位的電力，此時 (W1, W2, W3) = (4, 5, 7)。排序完成後機器總共花費 11 + 9 = 20 單位的電力。
請幫管理員計算出需花費多少單位的電力來完成雕像的排序。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一列有一個正整數 N (3 ≤ N ≤ 2×105)，表示有 N 座雕像。第二列有 N 個正整數 W1, W2, …, WN (W1, W2, …, WN ≤ 106)，表示雕像的重量，兩個正整數之間以一個空白為間隔。 | 請輸出一個非負整數，表示機器需花費多少單位的電力來完成雕像的排序。 |
| 3 5 7 4 | 20 |
| 3 2 2 3 | 0 |
| 4 8 4 6 7 | 41 |
| 5 6 4 8 5 2 | 65 |
解題思路
本題如果使用 Bubble Sort 的方式來排序＋計算會超時，所以要使用 Murge Sort。並且本題的變數需要開 Long Long Int。
收資料的時候宣告一個全域的 Vector<long long int> num，並且將收到的資料存到這個 Vector 中。
使用遞迴的方式來做 Murge Sort，可以將遞迴命名為「murge」，遞迴的回傳值為一個 Vector<long long int>，雖然題目只要計算電力，但是還是需要經過排序的過程所以需要回傳值。
遞迴的參數需要兩個正數 l 和 r，分別代表左右邊界，要將陣列接成一半然後再來排序。首先判斷，if (l >= r)，代表陣列已經被切到只剩下一個資料了，所以宣告一個暫存 Vector<long long int>tmp，並且進行 tmp.push_back(num[l])，代表把這個只剩一個資料的數字存放到這個暫存 Vector 中，並且 return tmp。
如果陣列還有得切的話，就宣告一個整數 m = (l+r)/2，代表目前兩個邊界的中間點。之後要宣告兩個 vector<long long int>，分別是 left 跟 right，代表目前邊界切一半之後的樣子，left = murge(l, m)，right = murge(m+1, r)。這樣子就會再次呼叫遞迴，並且會從只有一個資料的 Vector 開始做計算。
再來要宣告一個整數 lsum 代表 left 這個陣列中資料的總和，之後計算答案的時候會用到，可以使用 For迴圈 來計算 lsum。
先宣告兩個整數 l_index 和 r_index，都是預設為 0，這是我們等一下要取 left 和 right 中資料的順序。再來要跑一個 For迴圈，要跑 left.size() + right.size() 次，因為要將 left 和 right 中的資料排序好並且放到一個新的 Vector<long long int> final 中。主要的思路是判斷 left 和 right 中的資料哪一個比較小就先放到 final 中，可以參考下圖範例：
從上圖可以看到，「2」先和「1」做比較，因為「1」較小所以先將「1」放到 final 中。接下來進行「2」和「6」的比較，因為「2」較小，所以將「2」放到 final 中，以此類推。
要先判斷 l_index 是否 已經是 left.size() 了，這樣代表 left 的東西都已經放到 final 中了，再來還要先判斷 r_index 是否也已經是 right.size()了，這樣也不能放 right 中的資料。準確的判斷式會寫成：if (l_index == left.size() || (r_index != right.size() && right[r_index] < left[l_index]))。如果使從 left 取資料存放到 final，不會進行排序，但是如果是 right 中的資料比較小，就代表有進行交換的動作，也就需要電力。上面的判斷式就是屬於將 right 放到 final 中的判斷式。
如果有進行交換的動作，則需要計算花費了多少電力。首先要判斷這個數字要往左幾格，這個數值其實就是 left.size() – l_index，就是 left 還剩下多少數字的意思。再來要判斷往左走的時候經過了誰，這個就要用到剛剛宣告的「lsum」，因為 lsum 是 left 中的所有數字總和。花費的電力公式就會是：往左幾格*自己＋lsum。最後記得要將 r_index++，這樣下一次的 For迴圈 就會判斷 right 中的下一個資料。
如果是將 left 中的資料存到 final 中，lsum 要 -= left[l_index]，這樣子計算電力時才不會多計算其實已經放到 final 中的資料。記得也要將 l_index++。
最後 For迴圈 結束之後要回傳 final。在主程式的地方可以宣告一個 Vector<long long int> tmp = (0, N-1)，之後輸出 ans 即可。
範例程式碼－ZeroJudge N415: 雕像排序成本 (Sculpture)
#include <iostream>
#include <vector>
using namespace std;
vector<long long int>num;
long long int ans = 0;
vector<long long int> murge(const long long int l, const long long int r) {
if (l >= r) {
vector<long long int>tmp;
tmp.push_back(num[l]);
return tmp;
}
const long long int m = (l+r)/2;
const vector<long long int>left = murge(l, m), right = murge(m+1, r);
vector<long long int>final;
long long int lsum = 0, l_index = 0, r_index = 0;
for (const long long int i : left) lsum += i;
for (int i = 0; i<left.size()+right.size(); i++) {
if (l_index == left.size() || (r_index != right.size() && right[r_index] < left[l_index])) {
ans += (right[r_index]*(left.size()-l_index)) + lsum;
final.push_back(right[r_index]);
r_index++;
continue;
}
final.push_back(left[l_index]);
lsum -= left[l_index];
l_index++;
}
return final;
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
long long int N;
cin >> N;
for (long long int i = 0; i<N; i++)
{
long long int tmp;
cin >> tmp;
num.push_back(tmp);
}
vector<long long int>v = murge(0, N-1);
cout << ans << "\n";
}
//ZeroJudge N415
//Dr. SeanXD