a242: 第三題：絕對值總和的最小值

2021-06-27 20:03:51 +0800 CST Tags: math

出處：https://zerojudge.tw/ShowProblem?problemid=a242
提交：https://zerojudge.tw/Submissions?problemid=a242&account=allllllan123456

問題：給你一個正整數 $n\in[1,100000]$ 以及 $2n$ 個正整數 $a_1$, $x_1$, $a_2$, $x_2$, …, $a_n$, $x_n$，其中 $\displaystyle\sum_{i=1}^n a_i\le200000$ 而且 $a_i | x_i$ for all $i$，求 $\displaystyle\sum_{i=1}^n|a_ix - x_i|$ 的最小值。

解法：看到絕對值 $|x-x_i|$ 就要想成數線上 $x$ 和 $x_i$ 兩數的距離，因此我們可以先把原本的 $|a_ix - x_i|$ 都先解壓縮成 $a_i\cdot|x - x_i/a_i|$，原式於是展成 $\displaystyle\sum_{i=1}^{n'}|x - x_i'|$。讓 $x_1'\le x_2'\le …\le x_n'$，那麼讓頭尾兩兩一組，易知 $|x - x_1'| + |x - x_n'|$ 在 $x\in[x_1', x_n']$ 時會有最小值 $x_n' - x_1'$，而 $|x - x_2'| + |x - x_{n-1}'|$ 在 $x\in[x_2', x_{n-1}']$ 時有最小值 $x_{n-1}' - x_2'$，依此類推，因此當 $x$ 為 $x_1',\ x_2',\ …,\ x_n'$ 的中位數時能讓每一組都有各自的最小值，那它們加起來就是整體的最小值了。

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
 5    int m; cin >> m;
 6    while (m--) { long long ans = 0;
 7        int n; cin >> n; int vLen=0, v[200000];
 8        while (n--) {
 9            int a, x; cin >> a >> x;
10            int t = x / a;
11            while (a--) v[vLen++] = t;
12        }
13        sort(v, v+vLen);
14        for (int i=0; i<vLen-1-i; i++)
15            ans += v[vLen-1-i] - v[i];
16        cout << ans << '\n';
17    }
18    return 0;
19}