一种更好的“锦标赛”算法

Question

我有个问题。我已经为ZCO做了几天的准备，我遇到了一个非常简单的问题，我无法在3秒的时间内解决这个问题。问题来了：

N支球队参加在火星上举行的板球联赛，在那里，每一对不同的球队相互比赛一次。因此，总共有(N×(N_1))/2匹配。一位专家给每个团队分配了一个力量，一个正整数。奇怪的是，火星上的人群喜欢单面的比赛，而从一场比赛中获得的广告收入是两场比赛实力之差的绝对值。考虑到N队的实力，找到从所有比赛中获得的广告收入总额。 例如，假设N为4，团队1、2、3和4的团队实力分别为3、10、3和5。六场比赛的广告收入如下： 7，0，2，7，5，2 因此，广告收入总额为23。 样本输入4 3 10 3 5样本输出所有子任务中的23测试数据，每个团队的强度是1到1,000之间的整数。 子任务1 (30标记)：2≤N≤1,000。 子任务2(70分)：2≤N≤200,000。 限制 时限: 3s 内存限制: 64 MB

所以，我选择了一种简单的算法，它扫描并找到每个团队的广告收入，与之前的所有其他团队相对应。这相当于一个O(n^ 2 )，它不能传递子任务2。我不认为有可能对此进行改进，有人能帮我吗？

虽然没有什么帮助，但下面是我当前的C代码：

#include <stdio.h>

int main(void)
{
    long long int n, i, j;
    scanf("%lld", &n);
    long long int A[n], strength = 0;
    for(i = 0;i < n;i++)
    {
        scanf("%lld", &A[i]);
        for(j = i;j >= 0;j--)
        {
            strength += A[i] > A[j] ? A[i] - A[j] : A[j] - A[i];
        }
    }
    printf("%lld\n", strength);
    return 0;
}

Answer 1

假设我们有10支队伍，称他们为A，B，C，.，J从最强到最弱。让我们看一看A和J之间的匹配，它有一个有趣的特性:那场比赛的收入与另外两场比赛的收入之和相同，AB和BJ。还有AC和CJ。还有..。哇，通过把AJ乘以9，我们就有了所有比赛的收入总和，无论是A还是J！现在我们只剩下8支队伍了。让我们看看B对I的比赛，它有一个有趣的特性.数学不是很棒吗？