题解 | C. 终会再相见

C. 终会再相见

初中数学题，我们将 个人画在数轴上，重新排序

假设我们的相遇点为 ，将 这些人配对，记第 个人所处位置为

某一对 到 点相遇的代价为（假设 ）

其中 指 到距离较近的 或者 的距离的两倍，有

显然我们希望尽可能取第一种情况，不引入这个

容易发现此时不引入 的区间存在一个公共部分

我们只需要令 位于这个公共部分，就可以让所有情况下的 都不被引入了

当 为奇数时， 位于最中间点上 当 为偶数时， 位于最中间的两个点之间任意一个位置

笔者这里巧用了 0-index 和 1-index 的区别，从而较为方便地计算了上述中位数

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

typedef long long ll;

#define fType int
#define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++)
#define foreach_sub(x, a, b) for (fType x = a, _end_ = b; x >= _end_; x--)
#define tpl make_tuple

constexpr ll N = 100010;
ll a[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    ll n;
    cin >> n;

    foreach (i, 0, n - 1)
        cin >> a[i];
    sort(a, a + n);

    int k = (n >> 1);
    ll ans = 0;
    foreach (i, 0, k - 1)
        ans += a[k] - a[i];
    foreach (i, k + 1, n - 1)
        ans += a[i] - a[k];

    cout << ans << "\n";

    return 0;
}