练55.4 沙堡

解题思路

目标高度可以任意排列，所以将初始高度与目标高度分别升序排序后对应配对。每对若升高按差乘X，降低按差乘Y。

正确性说明

单对费用可写成((X+Y)|a-b|+(X-Y)(b-a))/2，所有配对的第二项总和固定。最小化等价于最小化绝对差之和；数轴排序同序配对可通过消除交叉证明最优。

易错点

输入每行一对并不要求最终一一对应，允许重排目标；总花费用long long。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long X, Y;
    cin >> n >> X >> Y;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++)
        cin >> a[i] >> b[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    long long ans = 0;
    for (int i = 0; i < n; i++)
        ans += b[i] >= a[i] ? (b[i] - a[i]) * X : (a[i] - b[i]) * Y;
    cout << ans << "\n";
    return 0;
}