AtCoder Beginner Contest 261 F // 樹狀數組
題目鏈接：F – Sorting Color Balls (atcoder.jp)
題意：
有n個球，球有顏色和數字。對相鄰的兩球進行交換時，若顏色不同，需要花費1的代價。求將球排成數字不降的順序，所需的最小代價。
思路：
將完成排序所需的最小代價記作 cost，將顏色不同的逆序對（ i < j && xi > xj && ci ≠ cj ）數量記作 cnt ，則有 cost = cnt。證明如下：
-
可以構造出一種所需花費為 cnt 的排序方案：將這n個球按顏色切分，即切分成若干個顏色相同的連續區間，那麼將每個區間進行排序，不需要花費任何代價，然後再進行冒泡排序，則花費代價恰為 cnt。因此有 cost ≧ cnt 。
-
再證明 cost ≤ cnt ：依然先將各個顏色相同的連續區間進行排序，那麼不考慮顏色時，總的逆序對變為 cnt 。每次進行相鄰數交換，則逆序對數量的變化可能為：+1、0、-1，那麼要讓逆序對數量變為 0，至少需要 cnt 次交換，因此有 cost ≤ cnt。
那麼只需要求出 cnt：求出不考慮顏色時逆序對數量 totalCnt，在求出對於各個顏色，顏色相同的逆序對數量Cnti，因此：cnt = totalCnt – ∑Cnti 。
然後求逆序對，就是樹狀數組的經典應用了。
代碼：
#include <bits/stdc++.h> #define LL long long #define lowbit(x) (x & -x) using namespace std; const int N = 300010; int n, c[N]; vector<int> v[N]; int tr[N]; void add(int x, int c) { for(int i = x; i <= n; i += lowbit(i)) tr[i] += c; } LL sum(int x) { LL res = 0; for(int i = x; i; i -= lowbit(i)) res += tr[i]; return res; } int main() { cin >> n; for(int i = 1; i <= n; i++) scanf("%d", &c[i]); for(int i = 1; i <= n; i++) { int x; scanf("%d", &x); v[0].push_back(x); //v[0]存儲不考慮顏色時的值，後續求出不考慮顏色時的逆序對 v[c[i]].push_back(x); //v[ci]則存儲考慮顏色時的值，後續求出相同顏色下的逆序對 } LL ans = 0; for(int i = 0; i <= n; i++) { for(auto& x : v[i]) { ans = ans + (i ? -1 : 1) * (sum(n) - sum(x)); add(x, 1); } for(auto& x : v[i]) add(x, -1); } cout << ans << endl; return 0; }
