为了防止后排的同学开小差，老师安排所有的同学都坐在第一排。 班上原有 N 个同学，按照入学时间，第 i 个同学的学号是 i，对应的位置是 Xi。 为了收作业方便，老师希望班长的位置到所有同学的位置的距离总和尽量小（如果有多个同学的位置满足最小距离总和，班长总是被选为最早入学的那个）。 每次有同学转学加入，学号是使用当前最小未被分配的编号（比如下一个同学转学加入，他的学号会是 N+1），并且被安排到位置 Yi 就坐。 随着新同学加入，老师会重新选择班长，使得收作业要求（即班长的位置到所有同学的位置的距离总和尽量小）仍然得到满足。 问每次新同学加入后，应该选择哪位同学做班长。用c++做这道题

题目分析：

每次加入一个新同学后，要重新选择班长，使得班长到所有同学位置的距离总和最小。我们可以先假设班长为当前已有同学的中位数，计算出总距离，然后再将新同学加入已有同学序列中，重新计算中位数和总距离即可。

代码实现：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> pos(n);
    for (int i = 0; i < n; i++) {
        cin >> pos[i];
    }
    sort(pos.begin(), pos.end());
    int mid = pos[(n - 1) / 2];
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += abs(mid - pos[i]);
    }
    cout << ans << endl;
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        pos.insert(lower_bound(pos.begin(), pos.end(), x), x);
        n++;
        mid = pos[(n - 1) / 2];
        ans = 0;
        for (int i = 0; i < n; i++) {
            ans += abs(mid - pos[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

时间复杂度：$O(n^2)$。每次加入新同学后都需要重新计算中位数和总距离，需要遍历整个序列。

优化：

我们可以发现，每次加入新同学后，只有新同学前后的同学的位置会发生变化，其他同学的位置不变。因此，我们可以先对已有同学的位置进行排序，然后用二分查找找到新同学应该插入的位置，再计算新中位数和总距离。这样就可以将时间复杂度优化到$O(n\log n)$。

代码实现：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> pos(n);
    for (int i = 0; i < n; i++) {
        cin >> pos[i];
    }
    sort(pos.begin(), pos.end());
    int mid = pos[(n - 1) / 2];
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += abs(mid - pos[i]);
    }
    cout << ans << endl;
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        int idx = lower_bound(pos.begin(), pos.end(), x) - pos.begin();
        pos.insert(pos.begin() + idx, x);
        n++;
        if (n % 2 == 0) {
            mid = (pos[n / 2 - 1] + pos[n / 2]) / 2;
        } else {
            mid = pos[n / 2];
        }
        ans += abs(mid - x);
        ans -= abs(mid - pos[idx - 1]);
        ans -= abs(mid - pos[idx + 1]);
        cout << ans << endl;
    }
    return 0;
}

时间复杂度：$O(n\log n)$。每次加入新同学后只需要重新计算新中位数和总距离，其他同学的位置不用重新计算。