c++ - 谁能告诉我为什么这超过了 2 秒的时间限制？(短代码)

Question

我已经苦苦挣扎了2天。拜托，有人能告诉我为什么当我之后输入20000和0和40000数字时它超过了时间限制吗？我试图使变量类型尽可能大，但这似乎也无济于事。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    /*freopen("file.in", "r", stdin);
    freopen("file.out", "w" , stdout);*/
    long long int aux,i, n, k, j, total = 0;
    cin >> n >> k;
    long long int a[n], b[n], order[n];
    signed long long int profit[n];
    for(i = 0; i < n; i++)
        cin >> a[i];
    for(i = 0; i < n; i++)
        cin >> b[i];
    for(i = 0; i < n; i++)
        profit[i] = a[i] - b[i];
    for(i = 0; i < n; i++)
        order[i] = i;
    for(i = 0; i < n; i++)
        for(j = i + 1; j < n; j++)
            if(profit[order[i]] > profit[order[j]])
            {
                aux = order[i];
                order[i] = order[j];
                order[j] = aux;
            }
    if(k > 0)
        for(i = 0; i < k; i++)
        {
            total += a[order[i]];
        }

    for(i = k; i < n; i++)
    {
        if(profit[order[i]] < 0)
            total += a[order[i]];
        else
            total += b[order[i]];
    }
    cout << total;

    return 0;
}

Answer 1

您的代码复杂度为 O(n^2)，对于 N=20000 来说太多了。降低复杂性，用 Qsort 代替冒泡排序。尝试使用自定义比较函数的 std::sort。