CSES – Stick Lengths

題目連結

題意

有 n 根棍子，第 i 個棍子用 p[i] 表示。你可以把棍子加長或縮短，花費是你加長 / 縮短多少。問最少花費多少可以讓所以棍子都變一樣長。

解題方法

結論: 以中位數當作基準算出每個棍子與他的cost的總和。

為什麼呢?
讓我們來舉個例子:
給兩個整數 a, b，要把他們都變成一個數字c，並且cost (與題目定義的一樣) 要最小。

只要 c 是在兩個數字的中間，c 越靠近 a 一點，就會離 b 遠一點。
所以我們會發現只要 a <= c <= b，所需的cost都是一樣的。

在這題當中，我們想要整個陣列的cost最小。
那當我們排序完之後，只要基準點是陣列的中位數，我們就會讓基準點在所有數字中間。
a[0] <= 中位數 <= a[n-1]
a[1] <= 中位數 <= a[n-2]
實務上如果陣列長度是偶數，取中間兩個任一個都可以，原因也如上。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector <int> p(n);
    for(int &x : p) cin >> x;
    sort(p.begin(), p.end());
    long long t = p[n/2];
    long long ans = 0;
    for(int i = 0;i < n;i++){
        ans += abs(p[i]-t);
    }
    cout << ans << '\n';
}