题解

对于每名队员 $i$，需要计算它与所有 $j\ne i$ 的

$$\min(x_i+y_j,x_j+y_i)$$

之和．直接枚举队员对是平方复杂度；完整做法的关键是找出两种分工方式的比较只取决于一个一维关键字．

算法 0：枚举队员对

对每个 $i$ 枚举所有 $j\ne i$，直接计算两种分工方式的较小值并累加．每一对队员会在两人的答案中各计算一次．

时间复杂度为 $O(n^2)$，答案数组需要 $O(n)$ 空间．在 $n\le2000$ 时，最多约进行 $4\times10^6$ 次常数操作．

预期通过 subtask 1，预期得分为 $30$ 分．

算法 1：所有 $y_i=0$

此时

$$c(i,j)=\min(x_i,x_j)．$$

将所有 $x_i$ 从小到大排序，并记录原编号．假设 $x_i$ 排序后位于位置 $p$，其左侧元素对答案贡献自身的 $x_j$，其右侧元素各贡献 $x_i$．因此

$$ans_i=\sum_{j<p}x_j+(n-p-1)x_i．$$

用前缀和即可计算全部答案，再按原编号回填．时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$．

预期通过 subtask 2，预期得分为 $15$ 分．

算法 2：$x_i-y_i$ 已经有序

比较队员 $i,j$ 的两种分工：

$$x_i+y_j\le x_j+y_i$$

等价于

$$x_i-y_i\le x_j-y_j．$$

令 $d_i=x_i-y_i$．当输入已经满足 $d_1\le d_2\le\cdots\le d_n$ 时，对于固定位置 $i$：

• 若 $j<i$，则 $d_j\le d_i$，较小值为 $x_j+y_i$．
• 若 $j>i$，则 $d_i\le d_j$，较小值为 $x_i+y_j$．

于是

$$ans_i=\sum_{j<i}x_j+(i-1)y_i+(n-i)x_i+\sum_{j>i}y_j．$$

分别预处理 $x$、$y$ 的前缀和即可在线性时间计算全部答案．如果两个队员的 $d$ 相等，那么两种分工的耗时也相等，把它们分在公式的任意一侧都不影响结果．

时间复杂度为 $O(n)$，空间复杂度为 $O(n)$．

预期通过 subtask 3，预期得分为 $25$ 分．

算法 3：按 $x_i-y_i$ 排序

一般情况下，将每名队员保存为四元组

$$(x_i,y_i,d_i,i),\qquad d_i=x_i-y_i,$$

并按 $d_i$ 从小到大排序．排序后就满足算法 2 的条件，可以使用相同的前缀和公式．最后根据保存的原编号 $i$ 把答案放回输入顺序．

实现时，排序比较器必须使用严格弱序：当 $d$ 不同时按 $d$ 比较，当 $d$ 相同时可以按原编号比较．不能在比较器中直接使用“小于等于”．不过，并列元素在排序后的先后顺序不影响数学答案，因为它们之间两种分工的耗时相等．

正确性证明

引理 1： 对任意两名队员 $i,j$，若 $d_i\le d_j$，则 $c(i,j)=x_i+y_j$；若 $d_i\ge d_j$，则 $c(i,j)=x_j+y_i$．

证明： 由 $d_i=x_i-y_i$，有

$$d_i\le d_j \iff x_i-y_i\le x_j-y_j \iff x_i+y_j\le x_j+y_i．$$

所以 $d_i\le d_j$ 时第一种分工不慢于第二种；反向情况同理．当二者相等时，两种分工耗时相同．引理得证．

引理 2： 排序后位于位置 $p$ 的队员 $i$，其左侧所有队员的总贡献为

$$\sum_{j<p}x_j+p\,y_i,$$

右侧所有队员的总贡献为

$$(n-p-1)x_i+\sum_{j>p}y_j,$$

这里位置从 $0$ 开始编号．

证明： 左侧队员 $j$ 满足 $d_j\le d_i$，由引理 1，每个贡献为 $x_j+y_i$；共有 $p$ 个，求和得到第一式．右侧队员满足 $d_i\le d_j$，每个贡献为 $x_i+y_j$；共有 $n-p-1$ 个，求和得到第二式．两部分都不包含位置 $p$ 自己．引理得证．

定理： 算法输出的每个 $ans_i$ 都等于队员 $i$ 与其他 $n-1$ 名队员合作的总耗时．

证明： 排序后，除队员 $i$ 自己外的所有队员恰好被划分为其左侧和右侧两部分．由引理 2，算法用前缀和准确计算两部分中每一名队员的合作耗时，且没有遗漏、重复或计入自己．二者之和就是题目要求的 $ans_i$．最后仅按原编号重新排列答案，不改变数值．定理得证．

复杂度分析

排序需要 $O(n\log n)$ 时间；建立前缀和及计算答案需要 $O(n)$ 时间．总时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$．

单项合作耗时最大为 $2\times10^9$，一个答案可能达到约 $10^{15}$，前缀和和答案都必须使用 $64$ 位整数．

预期通过所有 subtask，预期得分为 $100$ 分．

参考代码

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

struct Athlete {
    std::int64_t x;
    std::int64_t y;
    std::int64_t difference;
    int original_index;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<std::int64_t> x(n), y(n);
    for (std::int64_t& value : x) {
        std::cin >> value;
    }
    for (std::int64_t& value : y) {
        std::cin >> value;
    }

    std::vector<Athlete> athletes(n);
    for (int i = 0; i < n; ++i) {
        athletes[i] = {x[i], y[i], x[i] - y[i], i};
    }
    std::sort(athletes.begin(), athletes.end(), [](const Athlete& left, const Athlete& right) {
        if (left.difference != right.difference) {
            return left.difference < right.difference;
        }
        return left.original_index < right.original_index;
    });

    std::vector<std::int64_t> prefix_x(n + 1, 0);
    std::vector<std::int64_t> prefix_y(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_x[i + 1] = prefix_x[i] + athletes[i].x;
        prefix_y[i + 1] = prefix_y[i] + athletes[i].y;
    }

    std::vector<std::int64_t> answer(n, 0);
    for (int i = 0; i < n; ++i) {
        const std::int64_t left_count = i;
        const std::int64_t right_count = n - i - 1LL;
        const std::int64_t left_contribution = prefix_x[i] + left_count * athletes[i].y;
        const std::int64_t right_y_sum = prefix_y[n] - prefix_y[i + 1];
        const std::int64_t right_contribution = right_count * athletes[i].x + right_y_sum;
        answer[athletes[i].original_index] = left_contribution + right_contribution;
    }

    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            std::cout << ' ';
        }
        std::cout << answer[i];
    }
    std::cout << '\n';
    return 0;
}