c++ - 如何减少以下代码在 C++ 中的执行时间？

Question

我编写的这段代码的执行时间为 3.664 秒，但时间限制为 3 秒。 问题是——

N 支球队参加了火星上的板球联赛，每支球队 一对截然不同的球队只互相比赛一次。因此，总共有 (N × (N1))/2 个匹配项。专家为每个团队分配了力量， 一个正整数。奇怪的是，火星人喜欢一边倒的比赛 一场比赛赚取的广告收入的绝对值是 两场比赛的实力差距。鉴于 N 个团队的实力，找出所有团队获得的总广告收入 比赛。

输入格式

第 1 行:单个整数 N。

第 2 行:N 个空格分隔的整数，N 个团队的实力。

#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int stren[200000];
    for(int a=0;a<n;a++)
            cin>>stren[a];
    long long rev=0;
    for(int b=0;b<n;b++)
    {
            int pos=b;
            for(int c=pos;c<n;c++)
            {
                    if(stren[pos]>stren[c])
                        rev+=(long long)(stren[pos]-stren[c]);
                    else
                        rev+=(long long)(stren[c]-stren[pos]);
            }
    }
    cout<<rev;
}             

你能给我一个解决方案吗？？

Answer 1

将循环重写为:

sort(stren);
for(int b=0;b<n;b++)
{
   rev += (2 * b - n + 1) * static_cast<long long>(stren[b]);
}

Live code here

它为什么有效
您的循环生成所有 2 对数字并将差值添加到 rev。所以在排序数组中，第 b^th 项被减去 (n-1-b) 次并被加 b 次。因此数字 2 * b - n + 1

---

可以有 1 个可能不需要的微优化:

sort(stren);
for(int b = 0, m = 1 - n; b < n; b++, m += 2)
{
   rev += m * static_cast<long long>(stren[b]);
}