数轴上的点选择问题 - 最小化距离总和

数轴上的点选择问题 - 最小化距离总和

问题描述:

小北和辰辰陷入了一个数轴。数轴上有 n 个点，第 i 个点坐落于 x'i'。请你选择一个点 y，使得 ∑'i=1'n ∣x'i'−y∣ 最小。请你求出 y 和这个最小值。

保证: n 为奇数，且题目中用到的所有值均为整数（包括答案）。

输入:

共读入 2 行：

• 第 1 行：1 个整数 n；
• 第 2 行：n 个整数 x'i'。

输出:

输出共 2 行：

• 第 1 行：1 个整数表示选择的点 y；
• 第 2 行：1 个整数表示最小的 ∑'i=1'n ∣x'i'−y∣。

示例:

输入数据 1:

5
-1 0 2 3 10

输出数据 1:

2
14

限制:

1 ≤ n, k ≤ 10'3'， ∣x'i'∣ ≤ 10'3'，保证 x'i' 严格单调递增。

C++ 代码:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i];
    }
    sort(points.begin(), points.end());
    int median = points[n/2];
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += abs(points[i] - median);
    }
    cout << median << endl;
    cout << sum << endl;
    return 0;
}

算法解释:

为了最小化所有点到 y 的距离之和，最佳选择是选择所有点的中位数。这是因为，选择一个点比中位数大的点，会导致更靠近中位数的点距离更远，而选择一个点比中位数小的点，会导致更远离中位数的点距离更远。

代码解释:

1. 读取输入数据，并将所有点存储在一个 vector 中。
2. 使用 sort 函数对 vector 排序。
3. 计算中位数，因为 n 为奇数，中位数就是排序后的 vector 中间的元素。
4. 计算所有点到中位数的距离之和。
5. 输出中位数和距离之和。